| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1280291 | PlayVoltz | Distributing Candies (IOI21_candies) | C++20 | 0 ms | 0 KiB |
#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
struct node{
int s, e, m, mx, mn, val;
node *l, *r;
node(int S, int E){
s=S, e=E, m=(s+e)/2;
mx=mn=val=0;
if (s!=e){
l = new node(s, m);
r = new node(m+1, e);
}
}
void up(int i, int v){
if (s==e){
val=mn=mx=v;
return;
}
if (i<=m)l->up(i, v);
else r->up(i, v);
val=l->val+r->val;
mn=min(l->mn+r->val, r->mn);
mx=max(l->mx+r->val, r->mx);
}
pii querymx(int left, int right){
if (s==left && e==right)return mp(mx, val);
if (right<=m)return l->querymx(left, right);
else if (left>m)return r->querymx(left, right);
pii ll=l->querymx(left, m), rr=r->querymx(m+1, right);
return mp(max(ll.fi+rr.se, rr.fi), ll.se+rr.se);
}
pii querymn(int left, int right){
if (s==left && e==right)return mp(mn, val);
if (right<=m)return l->querymn(left, right);
else if (left>m)return r->querymn(left, right);
pii ll=l->querymn(left, m), rr=r->querymn(m+1, right);
return mp(min(ll.fi+rr.se, rr.fi), ll.se+rr.se);
}
}*st;
vector<signed> distribute_candies(vector<signed> c, vector<signed> l, vector<signed> r, vector<signed> v){
int n=c.size();
vector<vector<pii> > updates(n+1);
for (int i=0; i<l.size(); ++i)updates[l[i]].pb(mp(i, -v[i])), updates[r[i]+1].pb(mp(i, 0));
st = new node(0, n);
vector<int> ans(n);
for (int i=0; i<n; ++i){
for (auto c:updates[i])st->up(c.fi, c.se);
int low=-1, high=n;
while (low+1<high){
int mid=(low+high)/2;
if (st->querymx(mid, n-1).fi-st->querymn(mid, n-1).fi>c[i])low=mid;
else high=mid;
}
if (low==-1)ans[i]=-st->querymn(0, n-1).fi;
else{
int mx=st->querymx(low, n-1).fi, mn=st->querymn(low, n-1).fi;
if (v[low]>0)ans[i]=c[i]-mx;
else ans[i]=-mn;
}
}
return ans;
}