제출 #423058

#제출 시각아이디문제언어결과실행 시간메모리
423058MDario커다란 상품 (IOI17_prize)C++11
93.81 / 100
86 ms6676 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], abi1[200001]; vector<int> v[200001]; void update_abi(int xf, int yf){ while(xf<=maxn){ abi[xf]+=yf; abi1[xf]+=yf; xf+=xf&(-xf); } return; } void update_abi1(int xf, int yf){ while(xf<=maxn){ abi1[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_ab11(int xf){ int cr=0; while(xf>0){ cr+=abi1[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)-abi1[cr+(1<<i)]<xf){ cf+=(1<<i)-abi1[cr+(1<<i)]; cr+=(1<<i); } } } return cr; } int find_best(int n) { if(n<=5000){ 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 < 500; i++) { v[i]=ask(i); if(v[i][0]+v[i][1]==0)return i; } int x=0; for(int i = 0; i < 500; i++){ x=max(x, v[i][0]+v[i][1]); } for(int i = 0; i < 500; i++){ if(v[i][0]+v[i][1]!=x){ update_abi(i+1, 1); } else update_abi1(i+1, 1); } int l, r, z, c[20]; for(int i=1; i*500<n; i++){ l=i*500; r=min(l+500-1, n-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--; } else break; } if(l>r||v[r][0]==query_abi1(r+1))continue; update_abi1(r+1, 1); c[0]=v[r][0]-query_abi1(r); for(int t=0; t<c[0]; t++){ r--; c[1]=l-query_ab11(l+1)+1; c[3]=r-query_ab11(r+1)+1; while(c[1]<=c[3]){ c[2]=(c[1]+c[3])/2; c[4]=query_abi2(c[2]); v[c[4]]=ask(c[4]); if(v[c[4]][0]+v[c[4]][1]!=x){ update_abi(c[4]+1, 1); if(v[c[4]][0]+v[c[4]][1]==0)return c[4]; break; } update_abi1(c[4]+1, 1); if(v[c[4]][0]==query_abi1(c[4]+1))c[1]=c[2]; else c[3]=c[2]-1; } } } } return 0; }

컴파일 시 표준 에러 (stderr) 메시지

prize.cpp: In function 'int find_best(int)':
prize.cpp:76:23: warning: unused variable 'z' [-Wunused-variable]
   76 |             int l, r, z, c[20];
      |                       ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...