Submission #931759

#TimeUsernameProblemLanguageResultExecution timeMemory
931759winter0101Teams (IOI15_teams)C++14
0 / 100
1280 ms414472 KiB
#include<bits/stdc++.h> using namespace std; #define all(fl) fl.begin(),fl.end() #define pb push_back #define fi first #define se second #define for1(i,j,k) for(int i=j;i<=k;i++) #define for2(i,j,k) for(int i=j;i>=k;i--) #define for3(i,j,k,l) for(int i=j;i<=k;i+=l) #define lb lower_bound #define ub upper_bound #define sz(a) (int)a.size() #define pii pair<int,int> #define pli pair<long long,int> #define gcd __gcd #define lcm(x,y) x*y/__gcd(x,y) #define pil pair<int,long long> struct node{ int l,r,val; node(){ l=r=-1,val=0; } }st[30000009]; int nnode=0; int build(int id,int l,int r){ if (l==r)return id; int mid=(l+r)>>1; st[id].l=build(id<<1,l,mid); st[id].r=build(id<<1|1,mid+1,r); return id; } int copy(int id){ st[++nnode]=st[id]; return nnode; } int update(int id,int l,int r,int u,int val){ if (l>u||r<u)return id; if (l==r){ int newnode=copy(id); st[newnode].val+=val; return newnode; } int mid=(l+r)>>1; int newnode=copy(id); st[newnode].l=update(st[id].l,l,mid,u,val); st[newnode].r=update(st[id].r,mid+1,r,u,val); st[newnode].val=st[st[newnode].l].val+st[st[newnode].r].val; return newnode; } int update_range(int id1,int id2,int l,int r,int u,int v){ if (l>v||r<u||u>v)return id1; if (u<=l&&r<=v)return id2; int mid=(l+r)>>1; int newnode=copy(id1); st[newnode].l=update_range(st[id1].l,st[id2].l,l,mid,u,v); st[newnode].r=update_range(st[id1].r,st[id2].r,mid+1,r,u,v); st[newnode].val=st[st[newnode].l].val+st[st[newnode].r].val; return newnode; } int get(int id,int l,int r,int u,int v){ if (l>v||r<u||u>v)return 0; if (u<=l&&r<=v)return st[id].val; int mid=(l+r)>>1; return get(st[id].l,l,mid,u,v)+get(st[id].r,mid+1,r,u,v); } int walk(int id1,int id2,int l,int r,int val,int need){ if (st[id1].val-st[id2].val+val<need)return -1; if (l==r)return l; int mid=(l+r)>>1; int cost=st[st[id1].l].val-st[st[id2].l].val; if (cost+val>=need)return walk(st[id1].l,st[id2].l,l,mid,val,need); return walk(st[id1].r,st[id2].r,mid+1,r,val,need-cost); } const int maxn=5e5+9; pii a[maxn]; int req[maxn]; int root[maxn]; vector<int>add[maxn],del[maxn]; int n; void init(int N, int A[], int B[]) { n=N; for1(i,1,n){ a[i].fi=A[i-1],a[i].se=B[i-1]; } sort(a+1,a+1+n,[](pii p,pii q){ if (p.se==q.se)return p.fi<q.fi; return p.se<q.se; }); for1(i,1,n){ add[a[i].fi].pb(i); del[a[i].se+1].pb(i); int l=1,r=n; req[i]=n+1; while (l<=r){ int mid=(l+r)/2; if (a[mid].se>=i){ req[i]=mid; r=mid-1; } else l=mid+1; } } root[0]=build(1,1,n); nnode=4*n; for1(i,1,n){ int rt=root[i-1]; for(auto v:add[i]){ rt=update(rt,1,n,v,1); } for (auto v:del[i]){ rt=update(rt,1,n,v,-1); } root[i]=rt; } } int cnt[maxn]; int can(int M, int K[]) { int now=root[0],num=nnode; for1(i,0,M-1)cnt[K[i]]++; long long sum=0; for1(i,0,M-1)sum+=K[i]; if (sum>n)return 0; vector<int>gr; for1(i,0,M-1)gr.pb(K[i]); sort(all(gr)); gr.resize(distance(gr.begin(),unique(all(gr)))); bool fl=true; for (auto v:gr){ int ans=walk(root[v],now,1,n,get(root[v],1,n,1,req[v]-1)-get(now,1,n,1,req[v]-1),cnt[v]*v); if (ans==-1){ fl=false; break; } now=update_range(now,root[v],1,n,req[v],ans); } nnode=num; for1(i,0,M-1)cnt[K[i]]=0; return fl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...