Submission #66638

#TimeUsernameProblemLanguageResultExecution timeMemory
66638Bodo171Jousting tournament (IOI12_tournament)C++14
49 / 100
1075 ms26144 KiB
#include <vector> #include <iostream> using namespace std; const int nmax=200005; vector<int> v[nmax]; int l[nmax],r[nmax],aib[nmax],val[nmax],parinte[nmax],opt[nmax],ans[nmax]; int p[20][nmax]; int n,i,j,st,dr,act,nod,maxim,globalopt,mxx,par,Ss,D,pu,mx; inline int lbit(int x) { return ((x^(x-1))&x); } void update(int poz,int val) { for(int idx=poz;idx<=n;idx+=lbit(idx)) aib[idx]+=val; } int get_kth(int k) { int poz=0,curr=0; for(int p=16;p>=0;p--) if(poz+(1<<p)<=n&&curr+aib[poz+(1<<p)]<k) poz+=(1<<p),curr+=aib[poz]; poz++; return poz; } int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) { n=N; for(i=1;i<=n;i++) { update(i,1); } for(i=1;i<=n;i++) parinte[i]=C+i,opt[C+i]=i,l[C+i]=r[C+i]=i; for(i=1;i<=n-1;i++) val[i]=K[i-1]; for(i=1;i<=C;i++) { st=S[i-1]+1;dr=E[i-1]+1; l[i]=n;r[i]=0; for(j=dr;j>=st;j--) { act=get_kth(j); par=parinte[act]; if(l[par]<l[i]) l[i]=l[par]; if(r[par]>r[i]) r[i]=r[par]; p[0][par]=i; if(j==st) parinte[act]=i; else update(act,-1); } } for(i=1;i<=17;i++) for(j=1;j<=n+C;j++) p[i][j]=p[i-1][p[i-1][j]]; ans[0]=-1; for(i=1;i<=n;i++) { for(Ss=i-1;Ss>=1&&val[Ss]<R;Ss--); Ss++; for(D=i;D<n&&val[D]<R;D++); nod=C+i; for(pu=17;pu>=0;pu--) if(p[pu][nod]!=0&&Ss<=l[p[pu][nod]]&&r[p[pu][nod]]<=D) nod=p[pu][nod],ans[i]+=(1<<pu); if(ans[i]>ans[mx]) mx=i; } return mx-1; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...