제출 #280456

#제출 시각아이디문제언어결과실행 시간메모리
280456amiratou마상시합 토너먼트 (IOI12_tournament)C++14
17 / 100
1087 ms2176 KiB
#include <bits/stdc++.h> using namespace std; int fen[100005],init[100005],nxt[100005],pr[100005],KK[100005],n; void update(int idx,int val){ for (int i = idx; i <= (n+1); i+=(i&(-i))) fen[i]+=val; } int get(int idx){ int h=0; for (int i = idx; i >= 1; i-=(i&(-i))) h+=fen[i]; return h; } int gimme(int nb,int l=0,int r=n){ nb++; int ans=-1; while(l<=r){ int med=(l+r)>>1; if(get(med+1)>=nb) r=med-1,ans=med; else l=med+1; } assert(ans!=-1); return ans; } int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) { vector<int> vec(N); n=N; for (int i = 1; i <= N; ++i) update(i,1),vec[i-1]=K[i-1]; update(N+1,1); for (int i = 1; i <= N+1; ++i)init[i]=fen[i]; int ans=-1,m=-1; for (int p = 0; p <= N; ++p) { int sum=0; for (int i = 1; i <= N+1; ++i){ if((i-1)<p)KK[i-1]=K[i-1]; else if((i-1)==p)KK[i-1]=R; else KK[i-1]=K[i-2]; fen[i]=init[i]; if(i!=1)pr[i-1]=i-2; if(i!=(N+1))nxt[i-1]=i; } vec.insert(vec.begin()+p,R); for (int i = 0; i < C; ++i) { int st=gimme(S[i]),e=gimme(E[i]); int ST=st; int maxi=-1,arg=-1; while(st!=e){ if(KK[st]>maxi)maxi=KK[st],arg=st; update(st+1,-1); st=nxt[st]; } if(KK[e]>maxi)maxi=KK[e],arg=e; update(e+1,-1); update(arg+1,1); sum+=(arg==p); if(ST)nxt[pr[ST]]=arg,pr[arg]=pr[ST]; if(e!=N)nxt[arg]=nxt[e],pr[nxt[e]]=arg; } if(sum>ans)ans=sum,m=p; vec.erase(vec.begin()+p); } return m; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...