Submission #92480

#TimeUsernameProblemLanguageResultExecution timeMemory
92480Retro3014Meetings (IOI18_meetings)C++17
19 / 100
4410 ms7280 KiB
#include "meetings.h" #include <vector> using namespace std; #define MAX_N 5000 #define INF 1000000000000000000LL typedef long long ll; int N, Q; int seg1[MAX_N*4+1]; ll seg2[MAX_N*4+1]; int two=1; void update1(int x, int y){ x+=two; while(x>0) {seg1[x]=max(seg1[x], y); x/=2;} } void update2(int x, ll y){ x+=two; while(x>0){seg2[x]+=y; x/=2;} } int maxi(int x, int y){ x+=two; y+=two; int ret=0; while(x<=y){ if(x==y) return max(ret, seg1[x]); if(x%2) ret=max(ret, seg1[x++]); if(!(y%2))ret=max(ret, seg1[y--]); x/=2; y/=2; }return ret; } ll sum(int x, int y){ x+=two; y+=two; ll ret=0; while(x<=y){ if(x==y) return ret+seg2[x]; if(x%2) ret+=seg2[x++]; if(!(y%2))ret+=seg2[y--]; x/=2; y/=2; }return ret; } #define MAX_N2 100004 vector<int> v; int Li[MAX_N2+1], Ri[MAX_N2+1]; ll seg[21][MAX_N2*4+1]; ll CL[21][MAX_N2+1], CR[21][MAX_N2+1]; void update(int h, int x, ll y){ x+=two; while(x>0) {seg[h][x]=min(seg[h][x], y); x/=2;} } ll min(int h, int x, int y){ x+=two; y+=two; ll ret=INF; while(x<=y){ if(x==y) return min(ret, seg[h][x]); if(x%2) ret=min(ret, seg[h][x++]); if(!(y%2)) ret=min(ret, seg[h][y--]); x/=2; y/=2; }return ret; } vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) { N=(int)H.size(); Q=(int)L.size(); vector<ll> C(Q); if(N<=5000 && Q<=5000){ for(int i=0; i<Q; i++) C[i]=INF; while(two<N) two*=2; for(int i=0; i<N; i++) update1(i, H[i]); for(int i=0; i<N; i++){ for(int j=1; j<two*2; j++){ seg2[j]=0; } for(int j=0; j<N; j++){ update2(j, maxi(min(i, j), max(i, j))); } for(int j=0; j<Q; j++){ if(i>=L[j] && i<=R[j]) C[j]=min(C[j], sum(L[j], R[j])); } } }else{ while(two<N) two*=2; for(int h=1; h<=20; h++) for(int i=1; i<two*2; i++) seg[h][i]=INF; for(int i=0; i<N; i++){ while(!v.empty() && H[v.back()]<H[i]){ Ri[v.back()]=i; v.pop_back(); }v.push_back(i); }while(!v.empty()) {Ri[v.back()]=N; v.pop_back();} for(int i=N-1; i>=0; i--){ while(!v.empty() && H[v.back()]<H[i]){ Li[v.back()]=i; v.pop_back(); }v.push_back(i); }while(!v.empty()){Li[v.back()]=-1; v.pop_back();} int l, r;ll d=0; for(int i=0; i<N; i++){ l=Li[i]; r=Ri[i]; d=(ll)(Ri[i]-Li[i]-1)*(ll)H[i]; for(int h=H[i]; h<=20; h++){ if(l!=-1 && H[l]==h){ d+=(ll)h*(l-Li[l]); l=Li[l]; } if(r!=N && H[r]==h){ d+=(ll)h*(Ri[r]-r); r=Ri[r]; } update(h, i, d+(ll)(1+l)*h+(ll)(N-r)*h); } } for(int h=1; h<=20; h++){ for(int i=0; i<N; i++){ if(Li[i]==-1) CL[h][i]=(ll)(i+1)*min(h, H[i]); else CL[h][i]=(ll)(i-Li[i])*min(h, H[i])+CL[h][Li[i]]; } for(int i=N-1; i>0; i--){ if(Ri[i]==N) CR[h][i]=(ll)(N-i)*min(h, H[i]); else CR[h][i]=(ll)(Ri[i]-i)*min(h, H[i])+CR[h][Ri[i]]; } } int Hl, Hr; for(int i=0; i<Q; i++){ C[i]=INF; l=L[i]; r=R[i]; while(Ri[l]<=R[i]) l=Ri[l]; Hl=l; while(Li[r]>=L[i]) r=Li[r]; Hr=r; l=L[i]; r=R[i]; while(Ri[l]<=R[i]){ C[i]=min(C[i], min(H[l], l, Ri[l]-1)-CL[H[l]][L[i]-1]-CR[H[Hl]][Hl]+(ll)H[Hl]*(R[i]-Hl+1)); l=Ri[l]; } while(Li[r]>=L[i]){ C[i]=min(C[i], min(H[l], Li[r]+1, r)-CR[H[l]][R[i]+1]-CL[H[Hr]][Hr]+(ll)H[Hr]*(Hl-L[i]+1)); r=Li[r]; } C[i]=min(C[i], min(H[Hl], Hl, Hr)-CL[H[Hl]][Li[i]-1]-CR[H[Hl]][Ri[i]+1]); } } return 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...