#include "teams.h" #include <algorithm> #include <stack> #include <vector> using namespace std; typedef pair<int,int> pi; int n; pi a[500005]; struct rtree{ int lim; vector<int> tree[1050000]; void init(int n){ for(lim = 1; lim <= n; lim <<= 1); for(int i=0; i<n; i++){ int pos = a[i].first + lim; while(pos){ tree[pos].push_back(a[i].second); pos >>= 1; } } } int nsum(int idx, int s, int e){ return (int)(upper_bound(tree[idx].begin(), tree[idx].end(), e) - lower_bound(tree[idx].begin(), tree[idx].end(), s)); } int query(int sx, int ex, int sy, int ey){ sx += lim; ex += lim; int ret = 0; while(sx < ex){ if(sx % 2 == 1) ret += nsum(sx++, sy, ey); if(ex % 2 == 0) ret += nsum(ex--, sy, ey); sx >>= 1; ex >>= 1; } if(sx == ex) ret += nsum(sx, sy, ey); return ret; } }rtree; void init(int N, int A[], int B[]) { n = N; for(int i=0; i<N; i++){ a[i] = pi(A[i], B[i]); } sort(a,a+n,[&](const pi &a, const pi &b){return a.second < b.second;}); rtree.init(n); sort(a,a+n); } stack<int> sx, sy, cnt; int can(int M, int K[]) { while(!sx.empty()){ sx.pop(); sy.pop(); cnt.pop(); } sort(K, K+M); sx.push(0); sy.push(n); cnt.push(0); for(int i=0; i<M; i++){ while(!sy.empty() && sy.top() < K[i]){ sx.pop(); sy.pop(); cnt.pop(); } int sum = K[i], st = K[i] - 1, ed = -1; while(!sx.empty()){ int minus = rtree.query(sx.top() + 1, K[i], st + 1, sy.top()) + cnt.top(); if(sum > minus) sum -= minus; else{ ed = sy.top(); break; } st = sy.top(); sx.pop(); sy.pop(); cnt.pop(); } if(ed == -1) return 0; int s = st, e = ed; while(s != e){ int m = (s + e) / 2; int val = rtree.query(sx.top() + 1, K[i], st+1, m); if(val < sum) s = m+1; else e = m; } int tmp = rtree.query(sx.top() + 1, K[i], st + 1, s) - sum; sx.push(K[i]); sy.push(s); cnt.push(tmp); } return 1; }