Submission #1053435

#TimeUsernameProblemLanguageResultExecution timeMemory
1053435LudisseyBikeparking (EGOI24_bikeparking)C++17
68 / 100
1097 ms40364 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<qR||l>qL) return; if(r<=qR&&l>=qL){ x->lazy=v; x->propagate(); 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); vector<int> Y(N); for (int i = 0; i < N; i++) cin >> X[i]; for (int i = 0; i < N; i++) cin >> y[i]; for (int i = 0; i < N; i++) Y[i]=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++) { int xsm=sm; 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]; cout<< "MADE " << sm-xsm << "\n"; for (int j = 0; j < N; j++) { cout<< query(root,0,N-1,j,j) << " "; } cout<<"\n"; kp[i]=0; } cout << "\n";*/ sm=0; for (int i = 0; i < N; i++) { int xsm=sm; int l=i-1; while(l>=0){ int df=min(Y[i],X[l]); X[l]-=df; Y[i]-=df; sm+=df; if(Y[i]==0) break; l--; } kp[i]+=Y[i]; //cout<< "MADE " << sm-xsm << "\n"; for (int j = 0; j < N; j++) { //cout<< X[j] << " "; } //cout<<"\n"; } for (int i = 0; i < N; i++){ int df=min(X[i],kp[i]); kp[i]-=df; sm-=kp[i]; } cout << sm << "\n"; return 0; }

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:118:13: warning: unused variable 'xsm' [-Wunused-variable]
  118 |         int xsm=sm;
      |             ^~~
#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...