Submission #875299

#TimeUsernameProblemLanguageResultExecution timeMemory
875299HuyQuang_re_ZeroTeams (IOI15_teams)C++14
0 / 100
1307 ms408100 KiB
#include <bits/stdc++.h> #define ll long long #define db long double #define II pair <ll,ll> #define III pair <ll,II> #define IV pair <vector <int>,vector <int> > #define TII pair <treap*,treap*> #define fst first #define snd second #define BIT(x,i) ((x>>i)&1) #define pi acos(-1) #define to_radian(x) (x*pi/180.0) #define to_degree(x) (x*180.0/pi) #define Log(x) (31-__builtin_clz((int)x)) #define LogLL(x) (63-__builtin_clzll((ll)x)) #include "teams.h" using namespace std; struct Persistent { Persistent *l,*r; int sum=0; void comp() { sum=l->sum+r->sum; } } *ver[500005]; Persistent *build(Persistent *u,int l,int r) { u=new Persistent(); if(l==r) return u; int mid=(l+r)>>1; u->l=build(u->l,l,mid); u->r=build(u->r,mid+1,r); return u; } Persistent *update(Persistent *u,int l,int r,int x) { Persistent *v=new Persistent(); v->l=u->l; v->r=u->r; v->sum=u->sum; if(l==r) v->sum++; else { int mid=(l+r)>>1; if(x<=mid) v->l=update(u->l,l,mid,x); else v->r=update(u->r,mid+1,r,x); v->comp(); } return v; } int st[4*500005]; Persistent *lz[4*500005]; void change(int id,Persistent *x) { lz[id]=x; st[id]=x->sum; } void down(int id) { Persistent *x=lz[id]; if(x==NULL) return ; change(id*2,x->l); change(id*2+1,x->r); lz[id]=NULL; } void updateIT(int id,int l,int r,int u,int v,Persistent *x) { if(u>r || v<l) return ; if(u<=l && r<=v) { change(id,x); return ; } down(id); int mid=(l+r)>>1; updateIT(id*2,l,mid,u,v,x->l); updateIT(id*2+1,mid+1,r,u,v,x->r); st[id]=st[id*2]+st[id*2+1]; } int getIT(int id,int l,int r,int u,int v,Persistent *x) { if(u>r || v<l) return 0; if(u<=l && r<=v) return x->sum-st[id]; down(id); int mid=(l+r)>>1; return getIT(id*2,l,mid,u,v,x->l)+getIT(id*2+1,mid+1,r,u,v,x->r); } int Find(int id,int l,int r,Persistent *x,int k) { if(l==r) return l; down(id); int mid=(l+r)>>1,t=x->l->sum-st[id]; if(t>=k) return Find(id*2,l,mid,x->l,k); return Find(id*2+1,mid+1,r,x->r,k-t); } int n,m,i,a[500005],b[500005],cnt,Endn[500005],q; vector <int> vec[500005]; void init(int _n,int _a[],int _b[]) { n=_n; for(i=0;i<n;i++) vec[_a[i]].push_back(_b[i]); ver[0]=build(ver[0],1,n); for(i=1;i<=n;i++) { for(int x:vec[i]) cnt++,ver[cnt]=update(ver[cnt-1],1,n,x); Endn[i]=cnt; } } int can(int m,int _a[]) { for(i=m;i>=1;i--) a[i]=_a[i-1]; sort(a+1,a+m+1); updateIT(1,1,n,1,n,ver[0]); for(i=1;i<=m;i++) { Persistent *u=ver[Endn[a[i]]]; int k=getIT(1,1,n,1,a[i]-1,u); if(getIT(1,1,n,1,n,u)<a[i]+k) return 0; int pos=Find(1,1,n,u,a[i]+k); updateIT(1,1,n,a[i],pos,u); } return 1; } /* int main() { freopen("teams.inp","r",stdin); freopen("teams.out","w",stdout); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n; for(i=0;i<n;i++) cin>>a[i]>>b[i]; init(n,a,b); cin>>q; while(q--) { cin>>m; for(i=0;i<m;i++) cin>>a[i]; cout<<can(m,a)<<'\n'; } } */

Compilation message (stderr)

teams.cpp: In function 'int can(int, int*)':
teams.cpp:104:13: warning: declaration of 'm' shadows a global declaration [-Wshadow]
  104 | int can(int m,int _a[])
      |         ~~~~^
teams.cpp:91:7: note: shadowed declaration is here
   91 | int n,m,i,a[500005],b[500005],cnt,Endn[500005],q;
      |       ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...