Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- using namespace std;
- const int maxn = 1e5 + 10;
- const int INF = 2e9;
- struct element {
- int difference, idx1, idx2, pos;
- element () {}
- element(int _difference, int _idx1, int _idx2, int _pos) {
- difference = _difference;
- idx1 = _idx1;
- idx2 = _idx2;
- pos = _pos;
- }
- };
- element my_merge(element A, element B) {
- if(A.difference == B.difference) {
- if(A.idx1 < B.idx1) {
- return A;
- }
- return B;
- }
- if(A.difference < B.difference) {
- return A;
- }
- return B;
- }
- element segment_tree[3 * maxn];
- void build_tree(int L, int R, int position) {
- if(L == R) {
- segment_tree[position] = element(INF, INF, INF, INF);
- }
- else {
- int middle = (L + R) / 2;
- build_tree(L, middle, 2 * position);
- build_tree(middle + 1, R, 2 * position + 1);
- segment_tree[position] = my_merge(segment_tree[2 * position], segment_tree[2 * position + 1]);
- }
- }
- // L R i L R j L R
- element query(int L, int R, int position, int i, int j) {
- if(i <= L and R <= j) {
- return segment_tree[position];
- }
- if(R < i or j < L) {
- return element(INF, INF, INF, INF);
- }
- int middle = (L + R) / 2;
- return my_merge(query(L, middle, 2 * position, i, j), query(middle + 1, R, 2 * position + 1, i, j));
- }
- void update(int L, int R, int position, int idx, element new_value) {
- if(L == R) {
- segment_tree[position] = new_value;
- return;
- }
- int middle = (L + R) / 2;
- if(idx <= middle) {
- update(L, middle, 2 * position, idx, new_value);
- }
- else {
- update(middle + 1, R, 2 * position + 1, idx, new_value);
- }
- segment_tree[position] = my_merge(segment_tree[2 * position], segment_tree[2 * position + 1]);
- }
- int n;
- int dance[maxn], type[maxn];
- int main(){
- ios_base::sync_with_stdio(false);
- cin >> n;
- for(int i = 0; i < n; i++) {
- cin >> dance[i];
- }
- for(int i = 0; i < n; i++) {
- cin >> type[i];
- }
- build_tree(0, n - 1, 1);
- for(int i = 0; i < n - 1; i++) {
- if(type[i] != type[i + 1]) {
- element e(abs(dance[i] - dance[i + 1]), i, i + 1, i);
- update(0, n - 1, 1, i, e);
- }
- }
- vector<bool> visited(n, false);
- vector<pair<int, int> > ans;
- while(true) {
- element c = query(0, n - 1, 1, 0, n - 1);
- if(c.difference == INF) {
- break;
- }
- if(visited[c.idx1] or visited[c.idx2]) {
- update(0, n - 1, 1, c.pos, element(INF, INF, INF, INF));
- continue;
- }
- ans.push_back(make_pair(c.idx1, c.idx2));
- visited[c.idx1] = true;
- visited[c.idx2] = true;
- int first_unvisited_left = c.idx1 - 1;
- int first_unvisited_right = c.idx2 + 1;
- bool L = false, R = false;
- while(first_unvisited_left >= 0) {
- if(!visited[first_unvisited_left]) {
- L = true;
- break;
- }
- first_unvisited_left--;
- }
- while(first_unvisited_right < n) {
- if(!visited[first_unvisited_right]) {
- R = true;
- break;
- }
- first_unvisited_right++;
- }
- if(L and R and first_unvisited_left >= 0 and first_unvisited_right < n and !visited[first_unvisited_left] and !visited[first_unvisited_right]) {
- if(type[first_unvisited_left] != type[first_unvisited_right]) {
- element new_value(abs(dance[first_unvisited_left] - dance[first_unvisited_right]), first_unvisited_left, first_unvisited_right, c.pos);
- update(0, n - 1, 1, c.pos, new_value);
- }
- else {
- update(0, n - 1, 1, c.pos, element(INF, INF, INF, INF));
- }
- }
- else {
- update(0, n - 1, 1, c.pos, element(INF, INF, INF, INF));
- }
- }
- cout << (int) ans.size() << endl;
- for(int i = 0; i < (int) ans.size(); i++) {
- cout << ans[i].first + 1 << " " << ans[i].second + 1 << "\n";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement