Manioc

Untitled

Aug 31st, 2019
229
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.85 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define maxn 1000100
  4. #define ii pair<int, int>
  5. #define vii vector<ii>
  6.  
  7. bool lazy[4*maxn];
  8. int  st[4*maxn][2];
  9.  
  10. int left(int x){return 2*x;}
  11. int right(int x){return 2*x+1;}
  12.  
  13. void build(int id, int l, int r) {
  14.     st[id][1] = 0;
  15.     st[id][0] = r-l+1;
  16.     lazy[id] = 0;
  17.     if (l == r) return;
  18.     int mid = (l+r)/2;
  19.     build(left(id), l, mid);
  20.     build(right(id), mid+1, r);
  21. }
  22.  
  23. inline void propagate(int id, int l, int r) {
  24.     if (lazy[id]) {
  25.         st[id][1] = st[id][0];
  26.         st[id][0] = 0;
  27.         if (l != r) {
  28.             lazy[left(id)] = true;
  29.             lazy[right(id)] = true;
  30.         }
  31.     }
  32.     lazy[id] = 0;
  33. }
  34.  
  35. int query(int id, int l, int r, int start, int finish) {
  36.     cout << "qr\n";
  37.     printf("%d %d %d %d %d\n", id, l, r, start, finish);
  38.     propagate(id, l, r);
  39.     if (l > finish || r < start) return 0;
  40.     if (l >= start && r <= finish) return r-l+1 - st[id][0] - st[id][1];
  41.     int mid = (l+r)/2;
  42.     return
  43.         query(left(id), l, mid, start, finish) +
  44.         query(right(id), mid+1, r, start, finish);
  45. }
  46.  
  47. void update(int id, int l, int r, int start, int finish) {
  48.     // cout << "up\n";
  49.     // assert(min({l, r, start, finish}) >= 0);
  50.     propagate(id, l, r);
  51.     if (l > finish || r < start) return;
  52.     printf("up %d %d %d %d %d\n", id, l, r, start, finish);
  53.     if (l >= start && r <= finish) {
  54.         st[id][1] = st[id][0];
  55.         st[id][0] = 0;
  56.         lazy[left(id)] = true;
  57.         lazy[right(id)] = true;
  58.         return;
  59.     }
  60.     int mid = (l+r)/2;
  61.     update(left(id), l, mid, start, finish);
  62.     update(right(id), mid+1, r, start, finish);
  63.     st[id][0] = st[left(id)][0] + st[right(id)][0];
  64.     st[id][1] = st[left(id)][1] + st[right(id)][1];
  65. }
  66.  
  67. struct ev {
  68.     int x, y1, y2;
  69.     bool operator < (ev o) {
  70.         if (x != o.x) return x < o.x;
  71.         return y1 < o.y1;
  72.     }
  73. };
  74.  
  75. vii dots;
  76. int n,x,y;
  77.  
  78. int ans = 0;
  79. int solve() {
  80.     vector<ev> e;
  81.     for (int i = 0; i <= n; i++) {
  82.         int j = (i+1) % n;
  83.         if (dots[i].first == dots[j].first) {
  84.             e.push_back({dots[i].first, min(dots[i].second, dots[j].second), max(dots[i].second, dots[j].second)});
  85.  
  86.         }
  87.     }
  88.     int mi = 1e9;
  89.     for (auto u: e)
  90.         mi = min(mi, u.y1);
  91.     for (auto &u: e) {
  92.         u.y1 -= mi-1,
  93.         u.y2 -= mi-1;
  94.     }
  95.    
  96.     sort(e.begin(), e.end());
  97.     for (auto u: e) {
  98.         ans += query(1, 1, 1000010,u.y1, u.y2);
  99.         update(1, 1, 1000010,u.y1, u.y2);
  100.     }
  101. }
  102.  
  103. int main(){
  104.     cin >> n;
  105.     for (int i = 0; i < n; ++i) {
  106.         cin >> x >> y;
  107.         dots.push_back({x,y});
  108.     }
  109.     solve();
  110.     for (int i = 0; i , n; ++i) {
  111.         x = dots[i].first;
  112.         y = dots[i].second;
  113.         dots[i] = {-y, x};
  114.     }
  115.     solve();
  116.     cout << ans << '\n';
  117.        
  118.     return 0;
  119. }
Advertisement
Add Comment
Please, Sign In to add comment