Submission #1230181

#TimeUsernameProblemLanguageResultExecution timeMemory
1230181LudisseyDistributing Candies (IOI21_candies)C++20
0 / 100
781 ms27836 KiB
#include "candies.h" #include <bits/stdc++.h> using namespace std; #define all(a) (a.begin(), a.end()) #define rall(a) a.rbegin(), a.rend() #define sz(a) (int)a.size() struct node{ node* l; node* r; int mx,mn,lazy=0; void update(){ if(l!=NULL) { mn=min(mn,l->mn); mx=max(mx,l->mx); } if(r!=NULL) { mn=min(mn,r->mn); mx=max(mx,r->mx); } } }; struct segtree{ int n; node* root; void propagate(node* x){ if(x->l!=NULL) { x->l->lazy+=x->lazy; x->l->mn+=x->lazy; x->l->mx+=x->lazy; } if(x->r!=NULL) { x->r->lazy+=x->lazy; x->r->mn+=x->lazy; x->r->mx+=x->lazy; } x->lazy=0; } void build(node* x, int l, int r){ if(l==r) return; x->l=new node{NULL,NULL,0,0,0}; x->r=new node{NULL,NULL,0,0,0}; int mid=(l+r)/2; build(x->l,l,mid); build(x->r,mid+1,r); } void update(node* x, int l, int r, int qL, int qR, int v){ if(r<qL||l>qR) return; if(l>=qL&&r<=qR){ x->mx+=v; x->mn+=v; x->lazy+=v; return; } propagate(x); int mid=(l+r)/2; update(x->l,l,mid,qL,qR,v); update(x->r,mid+1,r,qL,qR,v); x->update(); } pair<int,int> query(node* x, int l, int r, int qL, int qR){ if(r<qL||l>qR) return {1e9,-1e9}; if(l>=qL&&r<=qR) return {x->mn,x->mx}; propagate(x); int mid=(l+r)/2; pair<int,int> u1=query(x->l,l,mid,qL,qR); pair<int,int> u2=query(x->r,mid+1,r,qL,qR); return {min(u1.first,u2.first),max(u1.second,u2.second)}; } segtree(int _n){ n=_n; root=new node{NULL,NULL,0,0,0}; build(root, 0, n-1); } void update(int l, int r, int v){ update(root,0,n-1,l,r,v); return; } pair<int,int> query(int l, int r){ return query(root,0,n-1,l,r); } }; std::vector<int> distribute_candies(std::vector<int> _c, std::vector<int> l, std::vector<int> r, std::vector<int> v) { int n = _c.size(); vector<int> s(n); int q=sz(l); segtree seg(q); int j=0; vector<pair<int,int>> sc(n); for (int i = 0; i < n; i++) sc[i]={_c[i],i}; sort(rall(sc)); for (int i = 0; i < q; i++) seg.update(i,q-1,v[i]); for (int i = 0; i < n; i++) { int c=sc[i].first; pair<int,int> qe=seg.query(j,q-1); while(qe.first<0||qe.second>c){ int vl=-1; int l=j; int r=q-1; int ans=-1; while(l<=r){ int mid=(l+r)/2; pair<int,int> qr=seg.query(j,mid); if(qr.first<0||qr.second>c){ ans=mid; if(qr.first<0) vl=qr.first; else if(qr.second>c) vl=qr.second; r=mid-1; }else{ l=mid+1; } } j=ans; if(vl<0) seg.update(ans,q-1,-vl); else seg.update(ans,q-1,c-vl); qe=seg.query(j,q-1); } s[sc[i].second]=seg.query(q-1,q-1).first; } return s; }
#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...