Submission #836870

#TimeUsernameProblemLanguageResultExecution timeMemory
836870Mohmad_ZaidMeetings (IOI18_meetings)C++17
36 / 100
1051 ms786432 KiB
// #include "meetings.h" #include <bits/stdc++.h> #define pb push_back #define ll long long #define print(a) for(int i=0;i<a.size();i++)cout<<a[i]<<endl; using namespace std; struct item{ ll pre=0,suf=0,seg=0; }; struct segtree{ int size=1; vector<item>arr; void init(int n){ while(size<n)size*=2; arr.resize(2*size-1); } void update(int i,int v,int x,int lx,int rx){ if(rx-lx==1){ int val=1; if(v==2)val=0; arr[x].pre=val; arr[x].suf=val; arr[x].seg=val; return; } int mid=(lx+rx)/2; if(i<mid)update(i,v,2*x+1,lx,mid); else update(i,v,2*x+2,mid,rx); arr[x].seg=max({arr[2*x+1].seg,arr[2*x+2].seg,arr[2*x+1].suf+arr[2*x+2].pre}); if(arr[2*x+1].pre==(rx-lx)/2){ arr[x].pre=arr[2*x+1].pre+arr[2*x+2].pre; }else{ arr[x].pre=arr[2*x+1].pre; } if(arr[2*x+2].suf==(rx-lx)/2){ arr[x].suf=arr[2*x+2].suf+arr[2*x+1].suf; }else{ arr[x].suf=arr[2*x+2].suf; } } void update(int i,int v){ update(i,v,0,0,size); } void get(int l,int r,int x,int lx,int rx,item& ans,int& vis){ if(lx>=r || rx<=l)return; if(lx>=l && rx<=r){ if(ans.seg+ans.pre+ans.suf==-3){ ans=arr[x]; }else{ ans.seg=max({ans.seg,arr[x].seg,ans.suf+arr[x].pre}); if(ans.pre==vis){ ans.pre=ans.pre+arr[x].pre; } if(arr[x].suf==rx-lx){ ans.suf=arr[x].suf+ans.suf; }else{ ans.suf=arr[x].suf; } } vis=rx-lx; return; } int mid=(lx+rx)/2; get(l,r,2*x+1,lx,mid,ans,vis); get(l,r,2*x+2,mid,rx,ans,vis); } void get(int l,int r,item& ans){ int vis=0; get(l,r,0,0,size,ans,vis); } void st_print(){ for(int i=0;i<2*size-1;i++){ cout<<i<<": "<<arr[i].pre<<' '<<arr[i].seg<<' '<<arr[i].suf<<endl; } } }; vector<long long> minimum_costs(vector<int> H, vector<int> L,vector<int> R) { int q = L.size(); int n = H.size(); ll mx=0; for(int i=0;i<n;i++)mx=max(mx,(ll)H[i]); if(mx<=2){ segtree st; st.init(n); vector<ll>C(q); for(int i=0;i<n;i++){ st.update(i,H[i]); } for(int i=0;i<q;i++){ item ans; ans.pre=-1;ans.seg=-1;ans.suf=-1; st.get(L[i],R[i]+1,ans); C[i]=(R[i]-L[i]+1-ans.seg)*2+ans.seg; } // st.st_print(); return C; }else{ vector<vector<ll>>suffix(n,vector<ll>(n+1,0)); vector<vector<ll>>prefix(n,vector<ll>(n+1,0)); vector<ll>C(q); for(int i=0;i<n;i++){ ll mx=0; for(int j=i;j<n;j++){ mx=max(mx,(ll)H[j]); suffix[i][j+1]=suffix[i][j]+mx; } mx=0; for(int j=i;j>=0;j--){ mx=max(mx,(ll)H[j]); prefix[i][j]=prefix[i][j+1]+mx; } } for(int i=0;i<q;i++){ ll mn=LONG_LONG_MAX; for(int j=L[i];j<=R[i];j++){ ll sm=0; sm+=H[j]; sm+=prefix[j][L[i]]-prefix[j][j]; sm+=suffix[j][R[i]+1]-suffix[j][j+1]; mn=min(mn,sm); } C[i]=mn; } return C; } } // int main(){ // vector<ll>c; // c=minimum_costs({2,1,2,1,1,1,2,1}, {2,0}, {6,3}); // print(c); // }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...