Submission #59570

#TimeUsernameProblemLanguageResultExecution timeMemory
59570ngkan146Teams (IOI15_teams)C++11
77 / 100
4046 ms171248 KiB
#include "teams.h" #include <bits/stdc++.h> using namespace std; const int N = 500005; typedef pair<int,int> ii; typedef pair<ii,int> iiI; #define fi first #define se second struct persistentSeg{ struct node{ int val, Lnode, Rnode; node(){} ~node(){} }; node seg[N * 25]; int root[N]; int totalNode; persistentSeg(){ for(int i=1;i<=2000000;i++){ seg[i].Lnode = 2*i; seg[i].Rnode = 2*i+1; } root[0] = 1; totalNode = 2000000; } int upd(int id,int l,int r,int pos,int value){ int newNode = ++totalNode; seg[newNode] = seg[id]; if (l == r){ seg[newNode].val += value; return newNode; } int mid = (l+r)/2; if (pos <= mid){ seg[newNode].Lnode = upd(seg[newNode].Lnode, l, (l+r)/2, pos, value); } else{ seg[newNode].Rnode = upd(seg[newNode].Rnode, (l+r)/2+1, r, pos, value); } seg[newNode].val = seg[seg[newNode].Lnode].val + seg[seg[newNode].Rnode].val; return newNode; } int get(int id,int l,int r,int u,int v){ if (v < l || r < u) return 0; if (u <= l && r <= v) return seg[id].val; return get(seg[id].Lnode, l, (l+r)/2, u, v) + get(seg[id].Rnode, (l+r)/2+1, r, u, v); } }; int n; ii range[N]; persistentSeg seg; vector <int> lis[N]; void init(int nn, int A[], int B[]) { n = nn; for(int i=0;i<n;i++){ lis[A[i]].push_back(B[i]); } for(int i=1;i<=n;i++){ seg.root[i] = seg.root[i-1]; for(auto v: lis[i]) seg.root[i] = seg.upd(seg.root[i], 1, n, v, 1); } } int currentInRange(int curRootId,int L,int R, const vector<iiI> &del){ int res = 0, cur = L; for(int i=0;;i++){ res += seg.get(seg.root[curRootId], 1, n, cur, min(del[i].fi.fi, R)) - seg.get(seg.root[del[i].fi.se], 1, n, cur, min(del[i].fi.fi, R)); res += (min(del[i].fi.fi, R) == del[i].fi.fi) * del[i].se; cur = del[i].fi.fi+1; if (cur > R) break; } return res; } int can(int m, int lst[]) { //~~~~~~~~~~~~~~~~prep~~~~~~~~~~~~~~~~~~~~~~ set <int> s; int tmp = 0; for(int i=0;i<m;i++){ tmp = min(n+1, tmp + lst[i]); s.insert(lst[i]); } if (tmp > n) return 0; int newM = 0; int ask[s.size()+5] = {}, askTimes[s.size()+5] = {}; for(set<int>::iterator it = s.begin(); it != s.end(); it++){ ask[++newM] = *it; } for(int i=0;i<m;i++){ askTimes[lower_bound(ask+1,ask+newM+1,lst[i]) - ask] ++; } //~~~~~~~~~~~~~~~solve~~~~~~~~~~~~~~~~~~~~~ vector <iiI> del; del.push_back({{n, 0}, 0}); for(int i=1;i<=newM;i++){ while(del.size() && del[0].fi.fi < ask[i]) del.erase(del.begin()); int L = ask[i]-1, R = n; while(L+1<R){ int mid = (L+R)/2; if (currentInRange(ask[i], ask[i], mid, del) < ask[i] * askTimes[i]) L = mid; else R = mid; } int curRes = currentInRange(ask[i], ask[i], R, del); if (curRes < ask[i] * askTimes[i]) return 0; while(del.size() && del[0].fi.fi <= R) del.erase(del.begin()); del.insert(del.begin(), {ii(R, ask[i]), curRes - ask[i] * askTimes[i]}); } return 1; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...