제출 #1020560

#제출 시각아이디문제언어결과실행 시간메모리
1020560simona1230휴가 (IOI14_holiday)C++17
30 / 100
221 ms9456 KiB
#include"holiday.h" #include<bits/stdc++.h> using namespace std; int a[100001],n,s,d; int tidx[100001],fl,fr; pair<int,int> p[100001]; long long ans; struct tree { long long act,val; tree(){} tree(int a,int v) { act=a; val=v; } }; tree t[400001]; void update(int i,int l,int r,int idx,int 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; } int 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(int i,int l,int r,int x) { if(t[i].act<=x)return t[i].val; int m=(l+r)/2; if(t[i*2].act<x) return query(i*2,l,m,x)+query(i*2+1,m+1,r,x-t[i*2].act); return query(i*2,l,m,x); } void change(int l,int 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(int l,int r,int optl,int optr) { if(l>r)return; int m=(l+r)/2; //cout<<m<<": "<<endl; long long maxx=-1,idxm=0; for(int 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; } } //cout<<m<<" "<<maxx<<" "<<idxm<<endl; div(l,m-1,optl,idxm); div(m+1,r,idxm,optr); } bool cmp(pair<int,int> p1,pair<int,int> 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(int i=0;i<n;i++) { a[i]=attraction[i]; p[i]={a[i],i}; } sort(p,p+n,cmp); for(int 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(int i=0;i<n;i++) p[i]={a[i],i}; sort(p,p+n,cmp); for(int i=0;i<n;i++) tidx[p[i].second]=i; for(int 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...