Submission #1020578

#TimeUsernameProblemLanguageResultExecution timeMemory
1020578simona1230Holiday (IOI14_holiday)C++17
47 / 100
5022 ms10328 KiB
#include"holiday.h" #include<bits/stdc++.h> using namespace std; long long a[100001],n,s,d; long long tidx[100001],fl,fr; pair<long long,long long> p[100001]; long long ans; struct tree { long long act,val; tree(){} tree(long long a,long long v) { act=a; val=v; } }; tree t[400001]; void update(long long i,long long l,long long r,long long idx,long long tp) { if(l==r) { //cout<<p[l].first<<" "<<tp<<endl; t[i].act=tp; if(t[i].act)t[i].val=p[l].first; else t[i].val=0; return; } long long m=(l+r)/2; if(idx<=m)update(i*2,l,m,idx,tp); else update(i*2+1,m+1,r,idx,tp); t[i].act=t[i*2].act+t[i*2+1].act; t[i].val=t[i*2].val+t[i*2+1].val; } long long query(long long i,long long l,long long r,long long x) { if(t[i].act<=x)return t[i].val; long long m=(l+r)/2; if(t[i*2].act<x) return t[i*2].val+query(i*2+1,m+1,r,x-t[i*2].act); return query(i*2,l,m,x); } void change(long long l,long long r) { //cout<<"c "<<fl<<" "<<fr<<" "<<l<<" "<<r<<endl; while(fl<l) { update(1,0,n-1,tidx[fl],0); fl++; } while(l<fl) { fl--; update(1,0,n-1,tidx[fl],1); } while(r<fr) { update(1,0,n-1,tidx[fr],0); fr--; } while(fr<r) { fr++; update(1,0,n-1,tidx[fr],1); } } void div(long long l,long long r,long long optl,long long optr) { if(l>r)return; long long m=(l+r)/2; //cout<<m<<": "<<endl; long long maxx=-1,idxm=0,last=0; for(long long i=optl;i<=optr;i++) { change(i,m); long long days=d-2*(m-s)-(s-i),val; if(days<=0)val=0; else val=query(1,0,n-1,days); //cout<<i<<" "<<m<<" "<<days<<" "<<val<<endl; ans=max(ans,val); if(val>maxx) { maxx=val; idxm=i; } if(val==maxx) { last=i; } } //cout<<m<<" "<<maxx<<" "<<idxm<<endl; div(l,m-1,optl,last); div(m+1,r,idxm,optr); } bool cmp(pair<long long,long long> p1,pair<long long,long long> p2) { return p1.first>p2.first; } long long int findMaxAttraction(int N, int start, int D, int attraction[]) { n=N; d=D; s=start; for(long long i=0;i<n;i++) { a[i]=attraction[i]; p[i]={a[i],i}; } sort(p,p+n,cmp); for(long long i=0;i<n;i++) tidx[p[i].second]=i; update(1,0,n-1,tidx[0],1); div(s,n-1,0,s); reverse(a,a+n); for(long long i=0;i<n;i++) p[i]={a[i],i}; sort(p,p+n,cmp); for(long long i=0;i<n;i++) tidx[p[i].second]=i; for(long long i=0;i<n;i++) update(1,0,n-1,i,0); update(1,0,n-1,tidx[0],1); fl=fr=0; s=n-s-1; div(s,n-1,0,s); 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...