#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
#define ln "\n"
#define ld long double
const ll inf=2e18;
struct segtree{
struct node{
ll mn, mx, upd;
node(){
mn=0;
mx=0;
upd=0;
}
void print(){
cout << "Printing: " << mn << " " << mx << " " << upd << "; ";
}
node(ll a, ll b, ll c) : mn(a),mx(b),upd(c){}
};
vector<node> t;
ll sz, rsz;
segtree(ll n){
sz=n*4; rsz=n;
t.resize(sz);
}
void preprocess(ll v, ll tl, ll tr){
if (t[v].upd){
// if (t[v].mn<inf)
t[v].mn+=t[v].upd;
// else t[v].mn=t[v].upd;
// if (t[v].mx>-inf)
t[v].mx+=t[v].upd;
// else t[v].mx=t[v].upd;
if (tl!=tr) {
t[v*2].upd+=t[v].upd;
t[v*2+1].upd+=t[v].upd;
}
t[v].upd=0;
}
}
node merge(node l, node r){
// l.print(); r.print();
node ret = node(min(l.mn, r.mn), max(l.mx, r.mx), 0ll);
// cout << "->"; ret.print();
// cout << ln;
return ret;
}
void update(ll tl, ll tr, ll v, ll l, ll r, ll x){
if (tl==l and tr==r){
t[v].upd+=x;
preprocess(v, tl, tr);
return;
}else if (l>r) {preprocess(v, tl, tr);return;}
preprocess(v, tl, tr);
ll tm = (tl+tr)/2;
update(tl, tm, v*2, l, min(r, tm), x);
update(tm+1, tr, v*2+1, max(l, tm+1), r, x);
t[v]=merge(t[v*2], t[v*2+1]);
}
void update(ll l, ll r, ll x){
update(0, rsz-1, 1, l, r, x);
}
void query(ll l, ll r, ll tl, ll tr, ll v, pair<ll, ll> &res){
if (tl==l and tr==r){
preprocess(v, tl, tr);
res.ff=min(res.ff, t[v].mn);
res.ss=max(res.ss, t[v].mx);
return;
}else if (l>r) {preprocess(v, tl, tr); return;}
preprocess(v, tl, tr);
ll tm = (tl+tr)/2;
query(l, min(tm, r), tl, tm, v*2, res);
query(max(l, tm+1), r, tm+1, tr, v*2+1, res);
}
pair<ll, ll> query(ll l, ll r){
// if (r==-1) return {0, 0};
// l=max(l, 0ll);
assert(l>-1 and r>-1);
pair<ll, ll> res={inf, -inf};
query(l, r, 0, rsz-1, 1, res);
return res;
}
void debug(ll tl, ll tr, ll v){
preprocess(v, tl, tr);
if (tl==tr){
cout << (t[v].mn==inf?-1:t[v].mn) << "-" << (t[v].mx==-inf?-1:t[v].mx) << " ";
}else{
cout << (t[v].mn==inf?-1:t[v].mn) << "-" << (t[v].mx==-inf?-1:t[v].mx) << "(";
ll tm=(tl+tr)/2;
debug(tl, tm, v*2);
debug(tm+1, tr, v*2+1);
cout << ") ";
}
}
void debug(){
debug(0, rsz-1, 1);
cout << ln;
}
};
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
ll n = c.size();
vector<vector<ll>> start(n), end(n);
// cout << n << endl;
l.insert(l.begin(), 0);
r.insert(r.begin(), n-1);
v.insert(v.begin(), 0);
for (ll i=0; i<(ll)l.size(); i++){
// cout << l[i] << "-" << r[i] << endl;
start[l[i]].push_back(i);
end[r[i]].push_back(i);
}
segtree tr(n);
vector<int> res(n);
for (ll i=0; i<n; i++){
for (auto j:start[i]){
// cout << "Hap" << j << ln;
tr.update(j, n-1, v[j]);
}
// tr.debug();
ll lo=-1, hi=n;
while (lo+1<hi){
ll mid = (lo+hi)/2;
pair<ll, ll> ret=tr.query(mid, n-1);
if (ret.ss-ret.ff>=c[i]) lo=mid;
else hi=mid;
}
// cout << i << ": " << lo << "::";
pair<ll, ll> ret = tr.query(max(lo, 0ll), n-1);
// cout << ret.ff << " " << ret.ss << ln;
if (lo==-1){
res[i] = (tr.query(n-1, n-1).ff-ret.ff);
}else if (tr.query(lo, lo).ff==ret.ff){
res[i] = c[i]-(ret.ss-tr.query(n-1, n-1).ff);
}else{
// cout << "Hap: " << tr.query(n-1, n-1).ff-ret.ff << ln;
res[i] = (tr.query(n-1, n-1).ff-ret.ff);
}
res[i]=min(c[i], max(0, res[i]));
for (auto j:end[i]){
tr.update(j, n-1, -v[j]);
}
}
return res;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
703 ms |
48316 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
45 ms |
13852 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
