제출 #69846

#제출 시각아이디문제언어결과실행 시간메모리
69846FedericoS마상시합 토너먼트 (IOI12_tournament)C++14
0 / 100
93 ms2864 KiB
#include <iostream> #include <vector> #include <assert.h> #include <set> using namespace std; typedef pair<int,int> pii; int N; int RT[4000005]; int inizio[400005],fine[400005]; pii ans; int P; set<int> Q; int query(int k, int l, int r, int a){ if(l==r) return l; int m=(l+r)/2; if(a<=RT[2*k]) return query(2*k, l, m, a); else return query(2*k+1, m+1, r, a-RT[2*k]); } void update(int k, int l, int r, int a, int b){ if(b<l or r<a) return; if(a<=l and r<=b){ RT[k]=0; return; } int m=(l+r)/2; update(2*k, l, m, a, b); update(2*k+1, m+1, r, a, b); RT[k]=RT[2*k]+RT[2*k+1]; } void costruisci(int k, int l, int r){ if(l==r){ RT[k]=1; return; } int m=(l+r)/2; costruisci(2*k,l,m); costruisci(2*k+1,m+1,r); RT[k]=RT[2*k]+RT[2*k+1]; } int converti(int k){ return query(1, 0, N, k+1); } void elimina(int x, int y){ update(1, 0, N, x, y); return; } int GetBestPosition(int N_, int C, int R, int *K, int *S, int *E) { N=N_; costruisci(1, 0, N); for(int i=0;i<C;i++){ S[i]=converti(S[i]); E[i]=converti(E[i]+1); elimina(S[i]+1,E[i]-1); } for(int i=0;i<C;i++) cout<<S[i]<<" "<<E[i]<<endl; for(int i=0;i<N-1;i++) if(K[i]>R) Q.insert(i); for(int i=0;i<C;i++) if(*Q.lower_bound(S[i])<E[i]-1) S[i]=E[i]=-1; for(int i=0;i<C;i++) if(S[i]!=-1){ inizio[S[i]]++; fine[E[i]]++; } for(int pos=0;pos<N;pos++){ P+=inizio[pos]; P-=fine[pos]; ans=max(ans,{P,-pos}); } return -ans.second; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...