Advertisement
erek1e

IOI '18 - Seats (37pts)

Jul 23rd, 2022
797
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.58 KB | None | 0 0
  1. #include "seats.h"
  2. #include <algorithm>
  3. #include <cassert>
  4. #include <iostream>
  5. #include <set>
  6.  
  7. using namespace std;
  8.  
  9. const int INF = 1e8;
  10. const int MX = 4e6 + 10; // maximum hw
  11. int h, w, n;
  12. vector<int> row, col;
  13.  
  14. int subtask = 6;
  15.  
  16. // SUBTASK 2
  17.  
  18. // SUBTASK 3
  19. struct Segtree {
  20.   int N, m;
  21.   int b[MX], t[MX], l[MX], r[MX];
  22.   void setSize(int sz) {
  23.     N = sz, m = 1;
  24.     while (m < N) m <<= 1;
  25.   }
  26.   Segtree(int sz) {setSize(sz);}
  27.   Segtree() {}
  28.   void build() {
  29.     for (int i = 0; i < m; ++i) {
  30.       if (i >= N) b[i] = l[i] = INF, t[i] = r[i] = -INF;
  31.       else {
  32.         b[m+i] = t[m+i] = row[i];
  33.         l[m+i] = r[m+i] = col[i];
  34.       }
  35.     }
  36.     for (int i = m-1; i > 0; --i) {
  37.       b[i] = min(b[2*i], b[2*i+1]);
  38.       t[i] = max(t[2*i], t[2*i+1]);
  39.       l[i] = min(l[2*i], l[2*i+1]);
  40.       r[i] = max(r[2*i], r[2*i+1]);
  41.     }
  42.   }
  43.   void update(int i) {
  44.     i += m;
  45.     b[i] = t[i] = row[i-m];
  46.     l[i] = r[i] = col[i-m];
  47.     while (i > 1) {
  48.       b[i>>1] = min(b[i], b[i^1]);
  49.       t[i>>1] = max(t[i], t[i^1]);
  50.       l[i>>1] = min(l[i], l[i^1]);
  51.       r[i>>1] = max(r[i], r[i^1]);
  52.       i >>= 1;
  53.     }
  54.   }
  55.   pair<pair<int, int>, pair<int, int>> query(int left, int right) {
  56.     int B = INF, T = -INF, L = INF, R = -INF;
  57.     for (left += m, right += m; left < right; left >>= 1, right >>= 1) {
  58.       if (left&1) {
  59.         B = min(B, b[left]);
  60.         T = max(T, t[left]);
  61.         L = min(L, l[left]);
  62.         R = max(R, r[left]);
  63.         left++;
  64.       }
  65.       if (right&1) {
  66.         --right;
  67.         B = min(B, b[right]);
  68.         T = max(T, t[right]);
  69.         L = min(L, l[right]);
  70.         R = max(R, r[right]);
  71.       }
  72.     }
  73.     return {{B, T}, {L, R}};
  74.   }
  75.   int queryGreater(int type, int limit) { // first index with value past some limit
  76.     if (type == 0 && b[1] >= limit) return N;
  77.     if (type == 1 && t[1] <= limit) return N;
  78.     if (type == 2 && l[1] >= limit) return N;
  79.     if (type == 3 && r[1] <= limit) return N;
  80.  
  81.     int i = 1;
  82.     while (i < m) {
  83.       int left = false;
  84.       if (type == 0 && b[2*i] < limit) left = true;
  85.       else if (type == 1 && t[2*i] > limit) left = true;
  86.       else if (type == 2 && l[2*i] < limit) left = true;
  87.       else if (type == 3 && r[2*i] > limit) left = true;
  88.       i <<= 1;
  89.       if (!left) ++i;
  90.     }
  91.     return i-m;
  92.   }
  93. };
  94. Segtree seg;
  95.  
  96. // SUBTASK 4
  97. int totalGood = 0;
  98. bool good[MX];
  99. void findGood(int l, int r) { // range [l, r)
  100.   for (int i = l; i < r; ++i) {  
  101.     // find the sidelengths of the segment
  102.     auto [p1, p2] = seg.query(0, i+1);
  103.     auto [B, T] = p1; auto [L, R] = p2;
  104.    
  105.     totalGood -= good[i];
  106.     good[i] = (T-B+1)*(R-L+1)-1 == i;
  107.     totalGood += good[i];
  108.   }
  109. }
  110.  
  111. void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
  112.   h = H, w = W, n = H*W, row = R, col = C;
  113.   if (n <= 10000) subtask = 2;
  114.   else if (h <= 1000 && w <= 1000) {
  115.     subtask = 3;
  116.     seg.setSize(n);
  117.     seg.build();
  118.   } else {
  119.     subtask = 4;
  120.     seg.setSize(n);
  121.     seg.build();
  122.     findGood(0, n);
  123.   }
  124. }
  125.  
  126. int swap_seats(int A, int B) {
  127.   if (subtask == 2) {
  128.     swap(row[A], row[B]);
  129.     swap(col[A], col[B]);
  130.     int beauty = 1;
  131.     int b = row[0], t = row[0], l = col[0], r = col[0];
  132.     for (int i = 1; i < n; ++i) {
  133.       b = min(b, row[i]);
  134.       t = max(t, row[i]);
  135.       l = min(l, col[i]);
  136.       r = max(r, col[i]);
  137.       if ((t-b+1)*(r-l+1) == (i+1)) ++beauty;
  138.     }
  139.     return beauty;
  140.   } else if (subtask == 3) {
  141.     swap(row[A], row[B]);
  142.     swap(col[A], col[B]);
  143.     seg.update(A);
  144.     seg.update(B);
  145.  
  146.     // main idea: sum of side lengths of good rectangles <= 2000 and strictly increasing
  147.     int beauty = 0;
  148.     int i = 0;
  149.     while (i < n) {
  150.       // i is the start of a new segment with equal sidelength sum
  151.       // first find the sidelengths of the segment
  152.       auto [p1, p2] = seg.query(0, i+1);
  153.       auto [B, T] = p1; auto [L, R] = p2;
  154.      
  155.       // now let us find the end of the segment
  156.       // i.e. find the first index after i with larger sidelength sum
  157.       int nextB = seg.queryGreater(0, B);
  158.       int nextT = seg.queryGreater(1, T);
  159.       int nextL = seg.queryGreater(2, L);
  160.       int nextR = seg.queryGreater(3, R);
  161.       int j = min({nextB, nextT, nextL, nextR}); // start of next segment
  162.  
  163.       assert((T-B+1)*(R-L+1)-1 >= j-1);
  164.       if ((T-B+1)*(R-L+1)-1 < j) ++beauty;
  165.       i = j;
  166.     }
  167.     return beauty;
  168.   } else { // Subtask 4
  169.     swap(row[A], row[B]);
  170.     swap(col[A], col[B]);
  171.     seg.update(A);
  172.     seg.update(B);
  173.     if (A > B) swap(A, B);
  174.     findGood(A, B);
  175.     return totalGood;
  176.   }
  177. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement