Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define loop(i,n) for(int i=0; i<n; i++)
- #define all(a) a.begin(),a.end()
- #define fr first
- #define sc second
- int INF=1e9;
- struct node{
- int he,l,r,ch;
- node ()
- {
- he = ch = INF;
- }
- };
- const int n = 5e5 * 4;
- node tree[n];
- pair <pair <int,int> , pair <int,int> > ar[50000];
- void push(int v)
- {
- if (tree[v].ch != INF && tree[v].l!=tree[v].r)
- {
- tree[v*2].he = tree[v].ch;
- tree[v*2+1].he = tree[v].ch;
- tree[v*2].ch = tree[v].ch;
- tree[v*2+1].ch = tree[v].ch;
- tree[v].ch = INF;
- }
- }
- void build_tree(int v, int l, int r)
- {
- if (l > r) return;
- tree[v].l = l; tree[v].r = r;
- if (l == r)
- {
- tree[v].he = -1;
- return;
- }
- int mid = (l + r)/2;
- build_tree(v*2, l, mid);
- build_tree(v*2+1, mid+1, r);
- tree[v].he = max (tree[v*2].he, tree[v*2+1].he);
- }
- int find_max(int v, int l)
- {
- push(v);
- if (tree[v].l > l || tree[v].r < l) return -1e5;
- if (tree[v].l == tree[v].r && tree[v].l == l) return tree[v].he;
- return max(find_max(v*2, l),find_max(v*2+1, l));
- }
- void upd(int v, int l, int r, int nw)
- {
- //cout << tree[v].ch;
- push(v);
- if (tree[v].l > r || tree[v].r < l) return;
- if (tree[v].l >= l && tree[v].r <= r)
- {
- tree[v].ch = nw;
- tree[v].he = nw;
- return;
- }
- //int mid = (l+r)/2;
- upd(v*2, l , r , nw);
- upd(v*2+1, l , r , nw);
- tree[v].he = max(tree[v*2].he, tree[v*2+1].he);
- }
- signed main()
- {
- int n;
- cin >> n;
- loop(i,50001)
- {
- ar[i].fr.fr = INF;
- ar[i].fr.sc = INF;
- ar[i].sc.fr = INF;
- ar[i].sc.sc = INF;
- }
- loop(i,n)
- {
- int x1,y1,x2,y2;
- cin >> x1 >> y1 >> x2 >> y2;
- ar[i].fr.fr = x1;
- ar[i].fr.sc = x2;
- ar[i].sc.fr = y1;
- ar[i].sc.sc = y2;
- }
- int ans=0;
- sort(ar, ar + 50001);
- build_tree(1, 0, 5e5);
- loop(i,n)
- {
- if (find_max(1,ar[i].sc.fr) < ar[i].fr.fr)
- {
- ans++;
- upd(1, ar[i].sc.fr, ar[i].sc.sc, ar[i].fr.sc);
- }
- }
- cout << ans;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement