//Challenge: Accepted
#include "candies.h"
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
using namespace std;
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ...b) {
cout << a << " ", debug(b ...);
};
template<class T> void pary (T l, T r) {
while (l!= r) cout << *l << " ", l++;
cout << endl;
};
#define ll long long
#define maxn 200005
#define pii pair<ll, ll>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
const ll inf = 1LL<<60;
struct segtree{
ll ma[4 * maxn], mi[4 * maxn], tag[4 * maxn];
int ama[4 * maxn], ami[4 * maxn];
void init(int cur, int l, int r) {
if (r <= l) return;
if (r - l == 1) {
ama[cur] = ami[cur] = l;
return;
}
int mid = (l + r) / 2;
init(cur * 2, l, mid), init(cur * 2 + 1, mid, r);
ama[cur] = ami[cur] = l;
}
void push(int cur, int l, int r) {
if (!tag[cur]) return;
ma[cur] += tag[cur], mi[cur] += tag[cur];
if (r - l > 1) tag[cur * 2] += tag[cur], tag[cur * 2 + 1] += tag[cur];
tag[cur] = 0;
}
void pull(int cur, int l, int r) {
push(cur, l, r);
if (r - l < 2) return;
int m = (l + r) / 2;
push(cur * 2, l, m), push(cur * 2 + 1, m, r);
if (ma[cur*2] > ma[cur*2+1]) ma[cur] = ma[cur*2], ama[cur] = ama[cur*2];
else ma[cur] = ma[cur*2+1], ama[cur] = ama[cur*2+1];
if (mi[cur*2] < mi[cur*2+1]) mi[cur] = mi[cur*2], ami[cur] = ami[cur*2];
else mi[cur] = mi[cur*2+1], ami[cur] = ami[cur*2+1];
}
void modify(int cur, int l, int r, int ql, int qr, ll val) {
if (r <= l || ql >= r || qr <= l) return;
push(cur, l, r);
if (ql <= l && qr >= r) {
tag[cur] += val;return;
}
int mid = (l + r) / 2;
modify(cur * 2, l, mid, ql, qr, val), modify(cur*2+1, mid, r, ql, qr, val);
pull(cur, l, r);
//debug("seg", l, r, ma[cur], mi[cur]);
}
pii search(int cur, int l, int r,ll big, ll small,ll c) { //maximum id
push(cur, l, r);
if (max(big, ma[cur]) - min(small, mi[cur]) <= c) return make_pair(-1, 0);
if (r - l == 1) {
return {l, (ma[cur] - small > c ? 0 : c)};
}
int m = (l + r) / 2;
if (max(ma[cur*2+1], big) - min(small, mi[cur*2+1]) > c) {
return search(cur*2+1, m, r, big, small, c);
} else {
return search(cur*2, l, m, max(ma[cur*2+1], big), min(small, mi[cur*2+1]), c);
}
}
pii getval(int cur, int l, int r, int ql, int qr) { //returns max, min of segment
if (r <= l || ql >= r || qr <= l) return {-inf, inf};
push(cur, l, r);
if (ql <= l && qr >= r) {
pull(cur, l, r);
return {ma[cur], mi[cur]};
}
int m = (l + r) / 2;
pii lef = getval(cur * 2, l, m, ql, qr), rig = getval(cur*2+1, m, r, ql, qr);
return make_pair(max(lef.ff, rig.ff), min(lef.ss, rig.ss));
}
}seg;
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
vector<pii> ch[maxn];
int n = c.size(), q = v.size();
vector<int> ret(n, 0);
for (int i = 0;i < q;i++) {
ch[l[i]].push_back({v[i], i+1});
ch[r[i] + 1].push_back({-v[i], i+1});
}
q++;
seg.init(1, 0, q);
for (int i = 0;i < n;i++) {
for (auto p:ch[i]) {
//debug("mod", p.ss, q, p.ff);
seg.modify(1, 0, q, p.ss, q, p.ff);
}
pii p = seg.search(1, 0, q, -inf, inf, c[i]), last = seg.getval(1, 0, q, q-1, q);
//debug(p.ff, p.ss);
if (p.ff == -1) {
pii all = seg.getval(1, 0, q, 0, q);
ret[i] = last.ff - all.ss;
//debug(0, last.ff, all.ss);
} else {
pii rem = seg.getval(1, 0, q, p.ff + 1, q);
if (p.ss == 0) ret[i] = last.ff - rem.ss;
else ret[i] = c[i] - (rem.ff - last.ff);
//debug(1, last.ff, rem.ff, rem.ss, p.ss);
}
}
return ret;
}
/*
3
10 15 13
6
0 2 20
0 1 -11
1 2 5
0 1 7
0 2 -14
0 2 11
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4940 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4940 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
5196 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
474 ms |
38932 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4940 KB |
Output is correct |
| 2 |
Incorrect |
295 ms |
35024 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4940 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4940 KB |
Output is correct |
| 3 |
Correct |
108 ms |
32448 KB |
Output is correct |
| 4 |
Correct |
81 ms |
7752 KB |
Output is correct |
| 5 |
Correct |
208 ms |
34948 KB |
Output is correct |
| 6 |
Correct |
215 ms |
35008 KB |
Output is correct |
| 7 |
Correct |
217 ms |
34992 KB |
Output is correct |
| 8 |
Correct |
227 ms |
34984 KB |
Output is correct |
| 9 |
Correct |
216 ms |
34992 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4940 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4940 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
5196 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
