제출 #429221

#제출 시각아이디문제언어결과실행 시간메모리
429221TLP39휴가 (IOI14_holiday)C++14
23 / 100
145 ms6580 KiB
#include"holiday.h" #include<bits/stdc++.h> using namespace std; typedef long long int ll; int n,d; int start; int a[100010]; map<int,int> mp; auto it=mp.begin(); ll tot_max=0,k=0; ll res; int st,ed,pos,p2; void movel(int x,int dl) { while(st>x) { st--; mp[a[st]]++; k-=dl; if(a[st]>(it->first)) { pos++; tot_max+=a[st]; } while(k<pos) { pos--; tot_max-=(it->first); p2--; if(!p2) { it++; p2=(it->second); } } while(k>pos) { if(it==mp.begin() && (it->second)==p2) break; pos++; p2++; if(p2>(it->second)) { it--; p2=1; } tot_max+=(it->first); } } while(st<x) { k+=dl; if(a[st]>(it->first) || (a[st]==(it->first) && p2==(it->second))) { pos--; tot_max-=a[st]; if(a[st]==(it->first)) { p2--; if(!p2) { if(it==mp.begin()) { it++; p2=(it->second); } else { it--; pos++; p2=1; tot_max+=(it->first); } } } } mp[a[st]]--; if(!mp[a[st]]) mp.erase(a[st]); while(k<pos) { pos--; tot_max-=(it->first); p2--; if(!p2) { it++; p2=(it->second); } } while(k>pos) { if(it==mp.begin() && (it->second)==p2) break; pos++; p2++; if(p2>(it->second)) { it--; p2=1; } tot_max+=(it->first); } st++; } } void mover(int y,int dr) { while(ed<y) { ed++; k-=dr; mp[a[ed]]++; if(a[ed]>(it->first)) { pos++; tot_max+=a[ed]; } while(k<pos) { pos--; tot_max-=(it->first); p2--; if(!p2) { it++; p2=(it->second); } } while(k>pos) { if(it==mp.begin() && (it->second)==p2) break; pos++; p2++; if(p2>(it->second)) { it--; p2=1; } tot_max+=(it->first); } } while(ed>y) { k+=dr; if(a[ed]>(it->first) || (a[ed]==(it->first) && p2==(it->second))) { pos--; tot_max-=a[ed]; if(a[ed]==(it->first)) { p2--; if(!p2) { if(it==mp.begin()) { it++; p2=(it->second); } else { it--; pos++; p2=1; tot_max+=(it->first); } } } } mp[a[ed]]--; if(!mp[a[ed]]) mp.erase(a[ed]); while(k<pos) { pos--; tot_max-=(it->first); p2--; if(!p2) { it++; p2=(it->second); } } while(k>pos) { if(it==mp.begin() && (it->second)==p2) break; pos++; p2++; if(p2>(it->second)) { it--; p2=1; } tot_max+=(it->first); } ed--; } } int test(int s,int l,int r,int dl,int dr) { if(l>r) return -1; if(dl*(start-s)+dr*(l-start)>d) return -1; int ans=l; ll temp_res; if(l<=ed) { mover(l,dr); movel(s,dl); } else { movel(s,dl); mover(l,dr); } temp_res=tot_max; for(int i=l+1;i<=r;i++) { if(dl*(start-s)+dr*(i-start)>d) break; mover(i,dr); if(tot_max>temp_res) { temp_res=tot_max; ans=i; } } res=max(res,temp_res); return ans; } void alltest(int l1,int r1,int l2,int r2,int dl,int dr) { if(l1>r1 || l2>r2) return; int temp; if(l1==r1) { temp=test(l1,l2,r2,dl,dr); return; } int mid=(l1+r1)>>1; temp=test(mid,l2,r2,dl,dr); alltest(l1,mid-1,l2,temp,dl,dr); alltest(mid+1,r1,temp,r2,dl,dr); } long long int findMaxAttraction(int N, int sta, int D, int attraction[]) { if(!D) return 0ll; if(D==1) return (ll)attraction[sta]; n=N; d=D; start=sta; for(int i=0;i<n;i++) a[i]=attraction[i]; st=sta; ed=sta; k=d; tot_max=res=(ll)a[sta]; mp[a[st]]=1; pos=1; p2=1; it=mp.begin(); alltest(max(0,sta-d),sta,sta,n-1,1,2); st=sta; ed=sta; k=d; tot_max=(ll)a[sta]; auto it3=mp.begin(); for(auto it2=mp.begin();it2!=mp.end();) { it3=it2; it2++; mp.erase(it3); } mp[a[st]]=1; pos=1; p2=1; it=mp.begin(); alltest(max(0,sta-d/2),sta,sta,n-1,2,1); return res; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...