Submission #422956

#TimeUsernameProblemLanguageResultExecution timeMemory
422956MDarioThe Big Prize (IOI17_prize)C++11
20 / 100
89 ms5908 KiB
#include "prize.h" #include<bits/stdc++.h> using namespace std; typedef long long ll; #define F first #define S second int maxn, abi[200001]; vector<int> v[200001]; void update_abi(int xf, int yf){ while(xf<=maxn){ abi[xf]+=yf; xf+=xf&(-xf); } return; } int query_abi1(int xf){ int cr=0; while(xf>0){ cr+=abi[xf]; xf-=xf&(-xf); } return cr; } int query_abi2(int xf){ int cr=0, cf=0; for(int i=18; i>=0; i--){ if(cr+(1<<i)<=maxn){ if(cf+(1<<i)-abi[cr+(1<<i)]<xf){ cf+=(1<<i)-abi[cr+(1<<i)]; cr+=(1<<i); } } } return cr; } int find_best(int n) { if(n<=4600){ for(int i = 0; i < n; i++) { vector<int> res = ask(i); if(res[0] + res[1] == 0) return i; } } else{ maxn=n; for(int i = 0; i < 460; i++) { v[i]=ask(i); if(v[i][0]+v[i][1]==0)return i; } int x=0, y=0; for(int i = 0; i < 460; i++){ x=max(x, v[i][0]+v[i][1]); } y=x; for(int i = 0; i < 460; i++){ if(v[i][0]+v[i][1]!=x){ y--; update_abi(i+1, 1); } } int l, r, z, c[20]; for(int i=1; i*460<n; i++){ l=i*460; r=min(l+460-1, n-1); z=l-query_abi1(l+1)+1; while(l<=r){ v[r]=ask(r); if(v[r][0]+v[r][1]!=x){ update_abi(r+1, 1); if(v[r][0]+v[r][1]==0)return r; r--; y--; } else break; } if(l>r||v[r][0]==query_abi1(r+1))continue; c[0]=v[r][0]-query_abi1(r); for(int t=0; t<c[0]; t++){ r--; c[1]=l; c[3]=r; while(c[1]<=c[3]){ c[2]=(c[1]+c[3])/2; c[4]=query_abi2(c[2]-l+z); v[c[4]]=ask(c[4]); if(v[c[4]][0]+v[c[4]][1]!=x){ y--; update_abi(c[4]+1, 1); if(v[c[4]][0]+v[c[4]][1]==0)return c[4]; break; } if(v[c[4]][0]==query_abi1(c[4]+1))c[1]=c[2]+1; else c[3]=c[2]-1; } } } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...