#include<bits/stdc++.h>
// #define DEBUG
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<int> vi;
typedef pair<ll, ll> pll;
struct query {
ll i;
ll t;
ll v;
bool operator< (const query& o) const {
return i < o.i;
}
};
struct Tree {
ll mn;
ll mx;
ll mn_ind;
ll mx_ind;
ll sum;
ll inc;
Tree* lt;
Tree* rt;
ll l, r;
Tree(ll a_l, ll a_r): l(a_l), r(a_r), lt(nullptr), rt(nullptr), mn(0), mx(0), sum(0), inc(0), mn_ind(0), mx_ind(0) {};
void push() {
if(inc == 0) return;
if(lt == nullptr) {
inc = 0;
return;
}
lt->inc += inc;
lt->mn += inc;
lt->mx += inc;
lt->sum += (lt->r - lt->l + 1) * inc;
rt->inc += inc;
rt->mn += inc;
rt->mx += inc;
rt->sum += (rt->r - rt->l + 1) * inc;
inc = 0;
}
void combine() {
mn = min(lt->mn, rt->mn);
mx = max(lt->mx, rt->mx);
if(lt->mn < rt->mn) mn_ind = lt->mn_ind;
else mn_ind = rt->mn_ind;
if(lt->mx > rt->mx) mx_ind = lt->mx_ind;
else mx_ind = rt->mx_ind;
sum = lt->sum + rt->sum;
}
void build() {
if(l == r) {
mn_ind = mx_ind = l;
return;
}
ll m = (l + r) >> 1;
lt = new Tree(l, m);
rt = new Tree(m + 1, r);
lt->build();
rt->build();
combine();
}
void upd(ll ql, ll qr, ll a_inc) {
if(ql > r || qr < l) return;
push();
if(ql == l && qr == r) {
inc += a_inc;
mn += a_inc;
mx += a_inc;
sum += (r - l + 1) * a_inc;
push();
return;
}
ll m = (l + r) >> 1;
lt->upd(ql, min(m, qr), a_inc);
rt->upd(max(m + 1, ql), qr, a_inc);
combine();
}
ll range_max(ll ql, ll qr) {
if(ql > r || qr < l) return numeric_limits<ll>::min();
push();
if(ql == l && qr == r) return mx;
ll m = (l + r) >> 1;
return max(lt->range_max(ql, min(m, qr)), rt->range_max(max(m + 1, ql), qr));
}
pll max_with_ind(ll ql, ll qr) {
if(ql > r || qr < l) return {-1ll, -1ll};
push();
if(ql == l && qr == r) return {mx_ind, mx};
ll m = (l + r) >> 1;
pll lind = lt->max_with_ind(ql, min(m, qr));
pll rind = rt->max_with_ind(max(m + 1, ql), qr);
if(lind.first == -1) return rind;
if(rind.first == -1) return lind;
if(lind.second > rind.second) return lind;
return rind;
}
ll ind_max(ll ql, ll qr) {
return max_with_ind(ql, qr).first;
}
ll range_min(ll ql, ll qr) {
if(ql > r || qr < l) return numeric_limits<ll>::max();
push();
if(ql == l && qr == r) return mn;
ll m = (l + r) >> 1;
return min(lt->range_min(ql, min(m, qr)), rt->range_min(max(m + 1, ql), qr));
}
pll min_with_ind(ll ql, ll qr) {
if(ql > r || qr < l) return {-1ll, -1ll};
push();
if(ql == l && qr == r) return {mn_ind, mn};
ll m = (l + r) >> 1;
pll lind = lt->min_with_ind(ql, min(m, qr));
pll rind = rt->min_with_ind(max(m + 1, ql), qr);
if(lind.first == -1) return rind;
if(rind.first == -1) return lind;
if(lind.second < rind.second) return lind;
return rind;
}
ll ind_min(ll ql, ll qr) {
return min_with_ind(ql, qr).first;
}
ll range_sum(ll ql, ll qr) {
if(ql > r || qr < l) return 0;
push();
if(ql == l && qr == r) return sum;
ll m = (l + r) >> 1;
return lt->range_sum(ql, min(m, qr)) + rt->range_sum(max(m + 1, ql), qr);
}
};
// IOI Function Signatures
vi distribute_candies(vi c, vi l, vi r, vi v) {
ll n = size(c);
ll q = size(l);
vector<query> queries;
for(ll i = 0; i < q; i++) {
queries.push_back({l[i], i, v[i]});
queries.push_back({r[i] + 1, i, -v[i]});
}
sort(queries.begin(), queries.end()); // Sort by array index
// Create a segtree of updates
Tree tr(0, q);
tr.build();
// Two pointer approach to adding queries
vi ans(n, 0);
ll p1 = 0, p2 = 0;
for(ll i = 0; i < n; i++) {
while(i > queries[p1].i) p1++;
p2 = p1;
while(i >= queries[p2].i) p2++;
for(ll j = p1; j < p2; j++) {
// #ifdef DEBUG
// cout << "ACTIVATING: " << queries[j].i << " " << queries[j].t << " " << queries[j].v << endl;
// #endif
tr.upd(queries[j].t + 1, q, queries[j].v);
}
ll l = -1, r = q + 1;
while(r - l > 1) {
ll m = (l + r) >> 1;
// #ifdef DEBUG
// cout << "MAXMIN " << m << ", " << tr.range_max(m, q - 1) << " " << tr.range_min(m, q - 1) << endl;
// #endif
if(tr.range_max(m, q) - tr.range_min(m, q) < c[i]) r = m;
else l = m;
}
#ifdef DEBUG
for(int j = 0; j <= q; j++) {
cout << tr.range_sum(j, j) << " ";
}
cout << endl;
#endif
if(r == 0) {
if(tr.range_max(r, q) >= c[i]) {
// #ifdef DEBUG
// cout << tr.range_sum(q, q) - tr.range_sum(0, 0) << endl;
// #endif
ll ind_max = tr.ind_max(r, q);
ans[i] = max(c[i] + tr.range_sum(q, q) - tr.range_sum(ind_max, ind_max), 0ll);
} else {
ll ind_min = tr.ind_min(r, q);
ans[i] = max(min(tr.range_sum(q, q) - tr.range_sum(ind_min, ind_min), (ll)c[i]), 0ll);
}
} else {
#ifdef DEBUG
cout << "BINSEARCH " << i << ", " << r << ", " << tr.range_min(l, q) << ", " << tr.range_max(l, q) << ", " << tr.range_sum(l, l) << endl;
#endif
ll left_elem = tr.range_sum(l, l);
ll range_min = tr.range_min(l, q);
ll range_max = tr.range_max(l, q);
#ifdef DEBUG
cout << "RANGE SUM: " << tr.range_sum(q, q) - tr.range_sum(r, r) << ", " << c[i] << endl;
#endif
if(left_elem == range_min) {
ll ind_max = tr.ind_max(l, q);
#ifdef DEBUG
cout << "IND MAX: " << ind_max << endl;
#endif
ans[i] = max(tr.range_sum(q, q) - tr.range_sum(ind_max, ind_max) + c[i], 0ll);
} else {
ll ind_min = tr.ind_min(l, q);
#ifdef DEBUG
cout << "IND MIN: " << ind_min << endl;
#endif
ans[i] = min(tr.range_sum(q, q) - tr.range_sum(ind_min, ind_min), (ll)c[i]);
}
}
// ans[i] = r;
}
return ans;
}
// Driver Function
#ifdef DEBUG
int main() {
int n;
cin >> n;
vi c(n, 0);
for(int& cv : c) {
cin >> cv;
}
int q;
cin >> q;
vi l(q, 0), r(q, 0), v(q, 0);
for(int i = 0; i < q ; i++) {
cin >> l[i] >> r[i] >> v[i];
}
vi ans = distribute_candies(c, l, r, v);
for(int i = 0; i < n; i++) {
cout << ans[i];
if(i < n - 1) cout << " ";
}
cout << endl;
return 0;
}
#endif
Compilation message
candies.cpp: In constructor 'Tree::Tree(ll, ll)':
candies.cpp:28:11: warning: 'Tree::r' will be initialized after [-Wreorder]
28 | ll l, r;
| ^
candies.cpp:26:11: warning: 'Tree* Tree::lt' [-Wreorder]
26 | Tree* lt;
| ^~
candies.cpp:30:5: warning: when initialized here [-Wreorder]
30 | Tree(ll a_l, ll a_r): l(a_l), r(a_r), lt(nullptr), rt(nullptr), mn(0), mx(0), sum(0), inc(0), mn_ind(0), mx_ind(0) {};
| ^~~~
candies.cpp:27:11: warning: 'Tree::rt' will be initialized after [-Wreorder]
27 | Tree* rt;
| ^~
candies.cpp:20:8: warning: 'll Tree::mn' [-Wreorder]
20 | ll mn;
| ^~
candies.cpp:30:5: warning: when initialized here [-Wreorder]
30 | Tree(ll a_l, ll a_r): l(a_l), r(a_r), lt(nullptr), rt(nullptr), mn(0), mx(0), sum(0), inc(0), mn_ind(0), mx_ind(0) {};
| ^~~~
candies.cpp:25:8: warning: 'Tree::inc' will be initialized after [-Wreorder]
25 | ll inc;
| ^~~
candies.cpp:22:8: warning: 'll Tree::mn_ind' [-Wreorder]
22 | ll mn_ind;
| ^~~~~~
candies.cpp:30:5: warning: when initialized here [-Wreorder]
30 | Tree(ll a_l, ll a_r): l(a_l), r(a_r), lt(nullptr), rt(nullptr), mn(0), mx(0), sum(0), inc(0), mn_ind(0), mx_ind(0) {};
| ^~~~
candies.cpp: In function 'vi distribute_candies(vi, vi, vi, vi)':
candies.cpp:221:16: warning: unused variable 'range_max' [-Wunused-variable]
221 | ll range_max = tr.range_max(l, q);
| ^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
2 ms |
860 KB |
Output is correct |
| 4 |
Correct |
2 ms |
860 KB |
Output is correct |
| 5 |
Correct |
5 ms |
856 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1219 ms |
56404 KB |
Output is correct |
| 2 |
Correct |
1312 ms |
54856 KB |
Output is correct |
| 3 |
Correct |
1323 ms |
55112 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 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 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
138 ms |
52820 KB |
Output is correct |
| 4 |
Correct |
254 ms |
3396 KB |
Output is correct |
| 5 |
Correct |
842 ms |
56244 KB |
Output is correct |
| 6 |
Correct |
823 ms |
56252 KB |
Output is correct |
| 7 |
Correct |
679 ms |
55332 KB |
Output is correct |
| 8 |
Correct |
830 ms |
55088 KB |
Output is correct |
| 9 |
Correct |
851 ms |
54456 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
2 ms |
860 KB |
Output is correct |
| 4 |
Correct |
2 ms |
860 KB |
Output is correct |
| 5 |
Correct |
5 ms |
856 KB |
Output is correct |
| 6 |
Correct |
1219 ms |
56404 KB |
Output is correct |
| 7 |
Correct |
1312 ms |
54856 KB |
Output is correct |
| 8 |
Correct |
1323 ms |
55112 KB |
Output is correct |
| 9 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
