Submission #1239951

#TimeUsernameProblemLanguageResultExecution timeMemory
1239951pcpJousting tournament (IOI12_tournament)C++20
0 / 100
1 ms1856 KiB
#include <iostream> #include <vector> #include <cstring> using namespace std; const int NN=100000; int tree[4*NN]; void in_updt(int node, int l, int r){ int m = (l + r)/2; if (l == r){ tree[node]=1; return; } in_updt(node*2, l, m); in_updt(node*2 + 1, m+1, r); tree[node] = tree[node*2]+tree[node*2+1]; } void update(int node, int l, int r, int x, int y){ int m = (l + r)/2; if (l>y || r<=x || tree[node]==0)return; if (l >x && r<=y ){ tree[node]=0; return; } update(node*2, l, m, x, y ); update(node*2 + 1, m+1, r, x, y ); tree[node] = tree[node*2]+tree[node*2+1]; } pair<int,int> query(int node, int l, int r, int x, int y, bool lx, bool ly){ int m = (l + r)/2; if (l==r)return {l,r}; if (lx && ly){ if (tree[node*2]>=y)return query(node*2,l,m,x,y,1,1); if (tree[node*2]<x)return query(node*2+1, m+1, r, x-tree[node*2],y-tree[node*2],1,1); return {query(node*2,l,m,x,0,1,0).first,query(node*2+1, m+1, r, 0,y-tree[node*2],0,1).second }; }else if (lx){ if (tree[node*2]>x)return query(node*2+1,m+1,r,x-tree[node*2],0,1,0); return query(node*2,l,m,x,0,1,0); }else if (ly){ if (tree[node*2]>=y)return query(node*2,l,m,0,y,0,1); else return query(node*2+1, m+1,r, 0, y-tree[node*2],0,1); }else return {-1,-1}; } int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) { memset(tree, 0, sizeof tree); in_updt(1,0,N-1); int mayores[N+10]; int c=0; mayores[0]=0; for (int i = 1 ; i < N;++i){ if (K[i-1]>R)c++; mayores[i]=c; //cout<<c<<" "; } mayores[N]=c; mayores[N+1]=c; //cout<<endl; // //if (1) return 0; // int zipline[N+10]; memset(zipline, 0, sizeof zipline); for (int i = 0 ; i < C; ++i){ pair<int,int> range = query(1,0,N-1,S[i],E[i],1,1); //cout<<S[i]<<" "<<E[i]<<" -> "<<range.first<<" "<<range.second<<" ->"; if (mayores[range.first] == mayores[range.second]){ zipline[range.first]+=1; zipline[range.second+1]-=1; //cout<<"[AC]"; }//else cout<<"[WA]"; //cout<<endl; update(1,0,N-1,range.first,range.second); //for (int i = 1; i < 20;++i)cout<<tree[i]<<" "; //cout<<endl; } c=0; int maxx=0; int maxxwho=0; for (int i = 0 ; i < N;++i){ c+=zipline[i]; //cout<<c<<" "; if (c>maxx){ maxx=c; maxxwho=i; } } //cout<<endl; return maxxwho; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...