Submission #1053444

#TimeUsernameProblemLanguageResultExecution timeMemory
1053444LudisseyBikeparking (EGOI24_bikeparking)C++17
100 / 100
921 ms38480 KiB
#include <bits/stdc++.h> #define int long long #define sz(a) (int)a.size() #define all(a) a.begin(), a.end() using namespace std; int N,M,Q; vector<int> X,y; struct node { node* left, *right; int sum, lazy; node(){ left=NULL; left=NULL; sum=0; lazy=-1; } void update(){ sum=left->sum+right->sum; } void propagate(){ if(lazy>-1){ sum=lazy; if(left!=NULL){ left->lazy=lazy; right->lazy=lazy; } lazy=-1; } } }; void build(node* x, int l, int r){ if(l==r) x->sum=X[l]; else{ x->left=new node(); x->right=new node(); int mid=(l+r)/2; build(x->left, l, mid); build(x->right, mid+1, r); x->update(); } } void update(node* x, int l, int r, int qL, int qR, int v){ x->propagate(); if(r<qL||l>qR) return; if(r<=qR&&l>=qL){ x->sum=v; x->lazy=v; return; } int mid=(l+r)/2; update(x->left, l, mid, qL, qR,v); update(x->right, mid+1, r, qL, qR,v); x->update(); } int query(node* x, int l, int r, int qL, int qR){ if(r<qL||l>qR) return 0; x->propagate(); if(r<=qR&&l>=qL){ return x->sum; } int mid=(l+r)/2; return query(x->left, l, mid, qL, qR)+query(x->right, mid+1, r, qL, qR); } signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> N; X.resize(N),y.resize(N); for (int i = 0; i < N; i++) cin >> X[i]; for (int i = 0; i < N; i++) cin >> y[i]; node* root = new node(); build(root,0,N-1); int sm=0; vector<int> kp(N,0); for (int i = 0; i < N; i++) { if(y[i]==0||i==0) {kp[i]+=y[i]; continue;} int l=0, r=i-1; while(l<r){ int mid=(l+r+1)/2; int q=query(root,0,N-1,mid,i-1); if(q>=y[i]){ l=mid; }else{ r=mid-1; } } if(l+1<i) { int q=query(root,0,N-1,l+1,i-1); y[i]-=q; sm+=q; update(root,0,N-1,l+1,i-1,0); } int q=query(root,0,N-1,l,l); int df=min(q,y[i]); sm+=df; y[i]-=df; update(root,0,N-1,l,l,q-df); kp[i]+=y[i]; } for (int i = 0; i < N; i++){ int df=min(query(root,0,N-1,i,i),kp[i]); kp[i]-=df; sm-=kp[i]; } cout << sm << "\n"; return 0; }
#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...