Advertisement
Josif_tepe

Untitled

May 23rd, 2023
953
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.18 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4. const int maxn = 1e5 + 10;
  5. const int INF = 2e9;
  6. struct element {
  7.     int difference, idx1, idx2, pos;
  8.     element () {}
  9.     element(int _difference, int _idx1, int _idx2, int _pos) {
  10.         difference = _difference;
  11.         idx1 = _idx1;
  12.         idx2 = _idx2;
  13.         pos = _pos;
  14.     }
  15. };
  16. element my_merge(element A, element B) {
  17.     if(A.difference == B.difference) {
  18.         if(A.idx1 < B.idx1) {
  19.             return A;
  20.         }
  21.         return B;
  22.     }
  23.     if(A.difference < B.difference) {
  24.         return A;
  25.     }
  26.     return B;
  27. }
  28. element segment_tree[3 * maxn];
  29. void build_tree(int L, int R, int position) {
  30.     if(L == R) {
  31.         segment_tree[position] = element(INF, INF, INF, INF);
  32.     }
  33.     else {
  34.         int middle = (L + R) / 2;
  35.         build_tree(L, middle, 2 * position);
  36.         build_tree(middle + 1, R, 2 * position + 1);
  37.         segment_tree[position] = my_merge(segment_tree[2 * position], segment_tree[2 * position + 1]);
  38.     }
  39. }
  40. // L R i L R j L R
  41. element query(int L, int R, int position, int i, int j) {
  42.     if(i <= L and R <= j) {
  43.         return segment_tree[position];
  44.     }
  45.     if(R < i or j < L) {
  46.         return element(INF, INF, INF, INF);
  47.     }
  48.     int middle = (L + R) / 2;
  49.     return my_merge(query(L, middle, 2 * position, i, j), query(middle + 1, R, 2 * position + 1, i, j));
  50. }
  51. void update(int L, int R, int position, int idx, element new_value) {
  52.     if(L == R) {
  53.         segment_tree[position] = new_value;
  54.         return;
  55.     }
  56.     int middle = (L + R) / 2;
  57.     if(idx <= middle) {
  58.         update(L, middle, 2 * position, idx, new_value);
  59.     }
  60.     else {
  61.         update(middle + 1, R, 2 * position + 1, idx, new_value);
  62.     }
  63.     segment_tree[position] = my_merge(segment_tree[2 * position], segment_tree[2 * position + 1]);
  64. }
  65. int n;
  66. int dance[maxn], type[maxn];
  67. int main(){
  68.     ios_base::sync_with_stdio(false);
  69.     cin >> n;
  70.     for(int i = 0; i < n; i++) {
  71.         cin >> dance[i];
  72.     }
  73.     for(int i = 0; i < n; i++) {
  74.         cin >> type[i];
  75.     }
  76.     build_tree(0, n - 1, 1);
  77.     for(int i = 0; i < n - 1; i++) {
  78.         if(type[i] != type[i + 1]) {
  79.             element e(abs(dance[i] - dance[i + 1]), i, i + 1, i);
  80.             update(0, n - 1, 1, i, e);
  81.         }
  82.     }
  83.     vector<bool> visited(n, false);
  84.     vector<pair<int, int> > ans;
  85.     while(true) {
  86.         element c = query(0, n - 1, 1, 0, n - 1);
  87.         if(c.difference == INF) {
  88.             break;
  89.         }
  90.         if(visited[c.idx1] or visited[c.idx2]) {
  91.             update(0, n - 1, 1, c.pos, element(INF, INF, INF, INF));
  92.             continue;
  93.         }
  94.         ans.push_back(make_pair(c.idx1, c.idx2));
  95.         visited[c.idx1] = true;
  96.         visited[c.idx2] = true;
  97.         int first_unvisited_left = c.idx1 - 1;
  98.         int first_unvisited_right = c.idx2 + 1;
  99.         bool L = false, R = false;
  100.         while(first_unvisited_left >= 0) {
  101.             if(!visited[first_unvisited_left]) {
  102.                 L = true;
  103.                 break;
  104.             }
  105.             first_unvisited_left--;
  106.         }
  107.         while(first_unvisited_right < n) {
  108.             if(!visited[first_unvisited_right]) {
  109.                 R = true;
  110.                 break;
  111.             }
  112.             first_unvisited_right++;
  113.         }
  114.         if(L and R and first_unvisited_left >= 0 and first_unvisited_right < n and !visited[first_unvisited_left] and !visited[first_unvisited_right]) {
  115.             if(type[first_unvisited_left] != type[first_unvisited_right]) {
  116.                 element new_value(abs(dance[first_unvisited_left] - dance[first_unvisited_right]), first_unvisited_left, first_unvisited_right, c.pos);
  117.                 update(0, n - 1, 1, c.pos, new_value);
  118.                
  119.             }
  120.             else {
  121.                 update(0, n - 1, 1, c.pos, element(INF, INF, INF, INF));
  122.             }
  123.         }
  124.         else {
  125.             update(0, n - 1, 1, c.pos, element(INF, INF, INF, INF));
  126.         }
  127.        
  128.     }
  129.     cout << (int) ans.size() << endl;
  130.     for(int i = 0; i < (int) ans.size(); i++) {
  131.         cout << ans[i].first + 1 << " " << ans[i].second + 1 << "\n";
  132.     }
  133.    
  134.     return 0;
  135. }
  136.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement