Submission #557221

#TimeUsernameProblemLanguageResultExecution timeMemory
557221n0sk1llRice Hub (IOI11_ricehub)C++14
100 / 100
278 ms72452 KiB
#include "ricehub.h" #include<bits/stdc++.h> using namespace std; long long int typedef li; //1-root obicnog, 2-root kurca li val[10000007],L[10000007],R[10000007],idx=2; void add(li p, li l, li r, li s, li x) { val[p]+=x; if (l==r) return; li mid=(l+r)/2; if (s<=mid) { if (!L[p]) L[p]=++idx; add(L[p],l,mid,s,x); } else { if (!R[p]) R[p]=++idx; add(R[p],mid+1,r,s,x); } } li sum(li p, li l, li r, li ll, li rr) { if (!p || ll>r || rr<l) return 0; if (ll<=l && rr>=r) return val[p]; li mid=(l+r)/2; return sum(L[p],l,mid,ll,rr)+sum(R[p],mid+1,r,ll,rr); } li walk(li p, li l, li r, li k) { if (l==r) return l; li mid=(l+r)/2; if (val[L[p]]>=k) return walk(L[p],l,mid,k); return walk(R[p],mid+1,r,k-val[L[p]]); } li balans(li m) { if (m<=0) return 0; li p=walk(1,1,1e18,m/2); return ((li)sum(1,1,1e18,1,p)*p-(li)sum(2,1,1e18,1,p))+((li)sum(2,1,1e18,p,1e18)-(li)sum(1,1,1e18,p,1e18)*p); } int besthub(int n, int useless, int x[], li b) { li l=0,r=0,mx=0; for (;r<n;r++) { add(1,1,1e18,x[r],1); add(2,1,1e18,x[r],x[r]); while (balans(r-l+2)>b) add(1,1,1e18,x[l],-1),add(2,1,1e18,x[l],-x[l]),l++; //cout<<"["<<l<<","<<r<<"] - "<<balans(r-l+2)<<endl; mx=max(mx,r-l+1); } return mx; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...