Submission #880572

#TimeUsernameProblemLanguageResultExecution timeMemory
880572khoquennguoiminhthuongHoliday (IOI14_holiday)C++14
100 / 100
200 ms48212 KiB
#include <bits/stdc++.h> using namespace std; int n; int a[100005]; int pos; int d; long long ans=0; struct node { int idl,idr,cnt; long long sum; }tree[2000005]; int goc[100005]; int timee; vector<long long>vec; void update(int nxt,int pre,int l,int r,int i,int val) { if(l>i||r<i||l>r)return ; if(l==r) { tree[nxt].sum=tree[pre].sum+val*vec[l-1]; tree[nxt].cnt=tree[pre].cnt+val; return; } int mid=(l+r)/2; if(i<=mid) { tree[nxt].idr=tree[pre].idr; tree[nxt].idl=++timee; update(tree[nxt].idl,tree[pre].idl,l,mid,i,val); } else { tree[nxt].idl=tree[pre].idl; tree[nxt].idr=++timee; update(tree[nxt].idr,tree[pre].idr,mid+1,r,i,val); } tree[nxt].cnt=tree[tree[nxt].idl].cnt+tree[tree[nxt].idr].cnt; tree[nxt].sum=tree[tree[nxt].idl].sum+tree[tree[nxt].idr].sum; //cout<<nxt<<" "<<tree[nxt].sum<<'\n'; } long long getsum(int nxt,int pre,int l,int r,int cnt) { if(cnt<=0)return 0; if(l==r)return 1LL*cnt*vec[l-1]; int mid=(l+r)/2; int vv=tree[tree[nxt].idr].cnt-tree[tree[pre].idr].cnt; if(vv>=cnt)return getsum(tree[nxt].idr,tree[pre].idr,mid+1,r,cnt); else return tree[tree[nxt].idr].sum-tree[tree[pre].idr].sum+getsum(tree[nxt].idl,tree[pre].idl,l,mid,cnt-vv); } void calc(int l,int r,int liml,int limr) { if(l>r)return ; int mid=(l+r)/2; long long val=-1; long long vt=liml; for(int i=liml;i<=limr;i++) { int ll=pos-mid; int rr=i-pos; int cnt=d-(ll+rr)-min(ll,rr); cnt=min(cnt,i-mid+1); if(cnt<0)continue; long long sum=getsum(goc[i],goc[mid-1],1,n,cnt); if(sum>val) {val=sum;vt=i;} } ans=max(ans,val); calc(l,mid-1,liml,vt); calc(mid+1,r,vt,limr); } long long findMaxAttraction(int _n,int _start,int _m,int _a[]) { n=_n; pos=_start; pos++; d=_m; for(int i=1;i<=n;i++)a[i]=_a[i-1]; for(int i=1;i<=n;i++)vec.push_back(a[i]); sort(vec.begin(),vec.end()); vec.erase(unique(vec.begin(),vec.end()),vec.end()); for(int i=1;i<=n;i++)a[i]=lower_bound(vec.begin(),vec.end(),a[i])-vec.begin()+1; for(int i=1;i<=n;i++) { goc[i]=++timee; update(goc[i],goc[i-1],1,n,a[i],1); } calc(1,pos,pos,n); return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...