#include<bits/stdc++.h>
#define pii pair<int,int>
#define f first
#define s second
#include "candies.h"
using namespace std;
const int N = 2e5 + 5;
long long lazy[4 * N];
struct node {
long long mx, mn, id1, id2;
} tree[4 * N], Z;
node merge(node a, node b) {
node c = {0,0,0,0};
if(a.mx > b.mx) c.mx = a.mx, c.id1 = a.id1;
else c.mx = b.mx, c.id1 = b.id1;
if(a.mn < b.mx) c.mn = a.mn, c.id2 = a.id2;
else c.mn = b.mn, c.id2 = b.id2;
return c;
}
void build(int u,int l,int r) {
if(l == r) {
tree[u].id1 = tree[u].id2 = l;
return;
}
int mid = (l + r)/2;
build(2 * u, l, mid); build(2 * u + 1,mid + 1,r);
tree[u] = merge(tree[2 * u], tree[2 * u + 1]);
}
void push(int u,int l,int r) {
tree[u].mx += lazy[u];
tree[u].mn += lazy[u];
if(l != r) {
lazy[2 * u] += lazy[u]; lazy[2 * u + 1] += lazy[u];
}
lazy[u] = 0;
}
void upd(int u,int st, int en,int l,int r,int val) {
push(u, l, r);
if(l > en || r < st) return;
if(st <= l && r <= en) {
lazy[u] = val;
push(u, l, r);
return;
}
int mid = (l + r)/2;
upd(2 * u,st,en,l,mid,val); upd(2 * u + 1,st,en,mid + 1,r,val);
tree[u] = merge(tree[2 * u], tree[2 * u + 1]);
}
node get(int u, int st, int en,int l,int r) {
push(u,l,r);
if(l > en || r < st) return Z;
if(st <= l && r <= en) return tree[u];
int mid = (l + r)/2;
return merge(get(2 * u,st,en,l,mid), get(2 * u + 1,st,en,mid + 1,r));
}
vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
std::vector<int> r, std::vector<int> v) {
int n = c.size(), q = r.size();
vector<int> s(n); Z.mn = 1e15;
vector<vector<pii> > st(n + 1), en(n + 1);
for(int i = 0; i < r.size(); i++) {
st[l[i]].push_back({i + 1, v[i]});
en[r[i] + 1].push_back({i + 1, -v[i]});
}
build(1,0,q);
for(int i = 0; i < n; i++) {
for(int j = 0; j < en[i].size(); j++) {
upd(1, en[i][j].f, q, 0, q, en[i][j].s);
// cout << "+" <<" " << en[i][j].f <<" " << en[i][j].s << endl;
}
for(int j = 0; j < st[i].size(); j++) {
upd(1,st[i][j].f, q, 0, q, st[i][j].s);
// cout << "-" <<" " << st[i][j].f <<" " << st[i][j].s << endl;
}
int last = 0;
{
int l = 1, r = q;
while(l <= r) {
int mid = (l + r)/2;
node g = get(1, mid - 1, q, 0, q);
if(g.mx - g.mn >= c[i]) {
l = mid + 1;
last = mid;
} else r = mid - 1;
}
}
int sum = 0, mn = 0, sum2 = 0;
for(int j = last; j < q; j++) {
if(l[j] <= i && i <= r[j]) {
sum += v[j];
mn = min(mn, sum);
}
}
if(last == 0) s[i] = sum - mn;
else if(v[last - 1] > 0) {
int sum = 0, F = q;
for(int j = last; j < q; j++) {
if(l[j] <= i && i <= r[j]) {
if(v[j] < 0) {
F = j;
break;
}
}
}
for(int j = F; j < q; j++) {
if(l[j] <= i && i <= r[j]) {
sum += v[j];
}
}
s[i] = c[i] + sum;
}
else {
int sum = 0, F = q;
for(int j = last; j < q; j++) {
if(l[j] <= i && i <= r[j]) {
if(v[j] > 0) {
F = j;
break;
}
}
}
for(int j = F; j < q; j++) {
if(l[j] <= i && i <= r[j]) {
sum += v[j];
}
}
s[i] = sum;
}
}
return s;
}
/*
int main() {
int n;
assert(1 == scanf("%d", &n));
std::vector<int> c(n);
for(int i = 0; i < n; ++i) {
assert(scanf("%d", &c[i]) == 1);
}
int q;
assert(1 == scanf("%d", &q));
std::vector<int> l(q), r(q), v(q);
for(int i = 0; i < q; ++i) {
assert(scanf("%d %d %d", &l[i], &r[i], &v[i]) == 3);
}
std::vector<int> ans = distribute_candies(c, l, r, v);
for(int i = 0; i < n; ++i) {
if (i > 0) {
printf(" ");
}
printf("%d", ans[i]);
}
printf("\n");
fclose(stdout);
return 0;
}*/
Compilation message
candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:62:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
62 | for(int i = 0; i < r.size(); i++) {
| ~~^~~~~~~~~~
candies.cpp:68:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
68 | for(int j = 0; j < en[i].size(); j++) {
| ~~^~~~~~~~~~~~~~
candies.cpp:72:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
72 | for(int j = 0; j < st[i].size(); j++) {
| ~~^~~~~~~~~~~~~~
candies.cpp:91:24: warning: unused variable 'sum2' [-Wunused-variable]
91 | int sum = 0, mn = 0, sum2 = 0;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
300 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
588 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5081 ms |
46216 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
300 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
588 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
