Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define maxn 1000100
- #define ii pair<int, int>
- #define vii vector<ii>
- bool lazy[4*maxn];
- int st[4*maxn][2];
- int left(int x){return 2*x;}
- int right(int x){return 2*x+1;}
- void build(int id, int l, int r) {
- st[id][1] = 0;
- st[id][0] = r-l+1;
- lazy[id] = 0;
- if (l == r) return;
- int mid = (l+r)/2;
- build(left(id), l, mid);
- build(right(id), mid+1, r);
- }
- inline void propagate(int id, int l, int r) {
- if (lazy[id]) {
- st[id][1] = st[id][0];
- st[id][0] = 0;
- if (l != r) {
- lazy[left(id)] = true;
- lazy[right(id)] = true;
- }
- }
- lazy[id] = 0;
- }
- int query(int id, int l, int r, int start, int finish) {
- cout << "qr\n";
- printf("%d %d %d %d %d\n", id, l, r, start, finish);
- propagate(id, l, r);
- if (l > finish || r < start) return 0;
- if (l >= start && r <= finish) return r-l+1 - st[id][0] - st[id][1];
- int mid = (l+r)/2;
- return
- query(left(id), l, mid, start, finish) +
- query(right(id), mid+1, r, start, finish);
- }
- void update(int id, int l, int r, int start, int finish) {
- // cout << "up\n";
- // assert(min({l, r, start, finish}) >= 0);
- propagate(id, l, r);
- if (l > finish || r < start) return;
- printf("up %d %d %d %d %d\n", id, l, r, start, finish);
- if (l >= start && r <= finish) {
- st[id][1] = st[id][0];
- st[id][0] = 0;
- lazy[left(id)] = true;
- lazy[right(id)] = true;
- return;
- }
- int mid = (l+r)/2;
- update(left(id), l, mid, start, finish);
- update(right(id), mid+1, r, start, finish);
- st[id][0] = st[left(id)][0] + st[right(id)][0];
- st[id][1] = st[left(id)][1] + st[right(id)][1];
- }
- struct ev {
- int x, y1, y2;
- bool operator < (ev o) {
- if (x != o.x) return x < o.x;
- return y1 < o.y1;
- }
- };
- vii dots;
- int n,x,y;
- int ans = 0;
- int solve() {
- vector<ev> e;
- for (int i = 0; i <= n; i++) {
- int j = (i+1) % n;
- if (dots[i].first == dots[j].first) {
- e.push_back({dots[i].first, min(dots[i].second, dots[j].second), max(dots[i].second, dots[j].second)});
- }
- }
- int mi = 1e9;
- for (auto u: e)
- mi = min(mi, u.y1);
- for (auto &u: e) {
- u.y1 -= mi-1,
- u.y2 -= mi-1;
- }
- sort(e.begin(), e.end());
- for (auto u: e) {
- ans += query(1, 1, 1000010,u.y1, u.y2);
- update(1, 1, 1000010,u.y1, u.y2);
- }
- }
- int main(){
- cin >> n;
- for (int i = 0; i < n; ++i) {
- cin >> x >> y;
- dots.push_back({x,y});
- }
- solve();
- for (int i = 0; i , n; ++i) {
- x = dots[i].first;
- y = dots[i].second;
- dots[i] = {-y, x};
- }
- solve();
- cout << ans << '\n';
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment