Submission #1261801

#TimeUsernameProblemLanguageResultExecution timeMemory
1261801PlayVoltzJousting tournament (IOI12_tournament)C++20
0 / 100
0 ms324 KiB
#include <bits/stdc++.h> using namespace std; struct fen{ int n; vector<int> ftt; fen(int N){ n=N; ftt.resize(n+1, 0); } void up(int i, int v){ for (;i<=n;i+=i&-i)ftt[i]+=v; } int sum(int i){ int res=0; for (int p=i;p;p-=p&-p)res+=ftt[p]; return res; } int bs(int v){ int res=n, id=0, sum=0; for (int i=20; i>=0; --i)if (id+(1<<i)<=n){ if (sum+ftt[id+(1<<i)]>=v)res=id+(1<<i); else id+=(1<<i), sum+=ftt[id]; } return res; } }*ft; int GetBestPosition(int n, int q, int k, int *K, int *L, int *R){ vector<int> vect(n+1), psum(n+1, 0), p(n+1, 1), d(n+1, 0); ft = new fen(n); for (int i=1; i<n; ++i)vect[i]=K[i-1]; for (int i=1; i<=n; ++i){ if (i!=1)psum[i]=psum[i-1]+(vect[i-1]>k); ft->up(i, 1); p[i]=i+1; } for (int i=0; i<q; ++i){ int l=ft->bs(L[i]+1), r=ft->bs(R[i]+1); for (int j=l+1; j<=r; j=p[j])ft->up(j, -1); p[l]=r+1; if (psum[l]==psum[r])++d[l], --d[r+1]; } int mx=0, best=0; for (int i=1, sum=0; i<=n; ++i){ sum+=d[i]; if (sum>mx)mx=sum, best=i-1; } return best; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...