Submission #31074

#TimeUsernameProblemLanguageResultExecution timeMemory
31074top34051Jousting tournament (IOI12_tournament)C++14
100 / 100
196 ms9516 KiB
#include<bits/stdc++.h> using namespace std; #define maxn 100005 int n; int sum[maxn], p[maxn], cnt[maxn]; int tree[maxn]; vector<int> temp; set<int> act; vector<pair<int,int> > a; void update(int x,int val) { x++; while(x<=n) { tree[x] += val; x += x&-x; } } int query(int x) { x++; int res = 0; while(x>0) { res += tree[x]; x -= x&-x; } return res; } int findpos(int x) { int l,r,mid,res=-1; l = 0; r = n-1; while(l<=r) { mid = (l+r)/2; if(query(mid)<=x) res = mid, l = mid+1; else r = mid-1; } return res; } int GetBestPosition(int N, int C, int X, int *K, int *L, int *R) { int i,j,l,r; pair<int,int> ans; set<int>::iterator it; n = N; for(i=0;i<n;i++) sum[i] = sum[i-1] + ((i<n-1 && K[i]>X) ? 1 : 0); for(i=0;i<n;i++) update(i,1), act.insert(i); for(i=0;i<C;i++) { l = findpos(L[i])+1; r = findpos(R[i]+1); // printf("%d : [%d, %d]\n",i,l,r); temp.clear(); for(it=act.find(l);it!=act.end() && *it<=r;++it) temp.push_back(*it); for(j=0;j<temp.size();j++) update(temp[j],-1), act.erase(temp[j]); update(l,1); act.insert(l); if(sum[r-1]-sum[l-1]==0) cnt[l]++, cnt[r+1]--; } ans = {0,0}; for(i=0;i<n;i++) cnt[i] += cnt[i-1], ans = max(ans,{cnt[i],-i}); return -ans.second; }

Compilation message (stderr)

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:52:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j=0;j<temp.size();j++) update(temp[j],-1), act.erase(temp[j]);
                  ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...