| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1126592 | VinhLuu | Distributing Candies (IOI21_candies) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
//#define ll long long
#define ll long long
#define all(lpv) lpv.begin(), lpv.end()
#define pot(x, y) lower_bound(x.begin(), x.end(), y) - x.begin() + 1
using namespace std;
//#define lpv
#ifndef lpv
#include "candies.h"
#endif // lpv
typedef pair<ll,ll> pii;
const ll N = 2e5 + 5;
ll n, q, h[N], a[N], L[N], R[N], C[N], mi[N << 2], mx[N << 2], lz[N << 2], st[N << 2];
vector<ll> open[N], close[N];
void update(ll i,ll l,ll r,ll u,ll x) {
if(l > r || r < u || u < l) return;
if(l == r) {
st[i] = x;
mx[i] = max(0ll, x);
mi[i] = min(0ll, x);
return;
}
ll mid = (l + r) / 2;
update(i << 1, l, mid, u, x);
update(i << 1|1, mid + 1, r, u, x);
mi[i] = min(mi[i << 1], st[i << 1] + mi[i << 1|1]);
mx[i] = max(mx[i << 1], st[i << 1] + mx[i << 1|1]);
st[i] = st[i << 1] + st[i << 1|1];
}
ll query(ll i,ll l,ll r,ll c) {
if(l == r) return min(max(0ll, st[i]), c);
ll mid = (l + r) / 2;
if(mx[i << 1|1] - mi[i << 1|1] > c) return query(i << 1|1, mid + 1, r, c);
ll ret = query(i << 1, l, mid, c);
if(ret + mx[i << 1|1] > c) return c - (mx[i << 1|1] - st[i << 1|1]);
if(ret + mi[i << 1|1] < 0) return st[i << 1|1] - mi[i << 1|1];
return ret + st[i << 1|1];
}
std::vector<ll> distribute_candies(std::vector<ll> _c, std::vector<ll> _l,
std::vector<ll> _r, std::vector<ll> _v) {
n = _c.size();
for(ll i = 1; i <= n; i ++) a[i] = _c[i - 1];
q = (ll)_l.size();
for(ll i = 1; i <= q; i ++) L[i] = _l[i - 1] + 1, R[i] = _r[i - 1] + 1, C[i] = _v[i - 1];
vector<ll> kq;
for(ll i = 1; i <= q; i ++) {
open[L[i]].push_back(i);
close[R[i] + 1].push_back(i);
}
for(ll i = 1; i <= n; i ++) {
for(auto j : open[i]) {
update(1, 1, q, j, C[j]);
}
for(auto j : close[i]) {
update(1, 1, q, j, 0);
}
kq.push_back({query(1, 1, q, a[i])});
}
return kq;
}
#ifdef lpv
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define task "v"
if(fopen(task ".inp","r")) {
freopen(task ".inp","r",stdin);
freopen(task ".out","w",stdout);
}
ll _n;
cin >> _n;
std::vector<ll> _c(_n);
for(ll i = 0; i < _n; ++i) {
cin >> _c[i];
}
ll _q;
cin >> _q;
std::vector<ll> _l(_q), _r(_q), _v(_q);
for(ll i = 0; i < _q; i ++) {
cin >> _l[i] >> _r[i] >> _v[i];
}
std::vector<ll> _ans = distribute_candies(_c, _l, _r, _v);
for(auto j : _ans) cout << j << " ";
}
#endif // lpv