#include "candies.h"
#include<bits/stdc++.h>
using namespace std;
#define int long long int
int segs[4*200005], segmx[4*200005], segmn[4*200005], lazy[4*200005];
void lazypropagate(int n, int l, int r) {
if (lazy[n]) {
segmn[n] += lazy[n];
segmx[n] += lazy[n];
if (l != r) {
lazy[2*n] += lazy[n];
lazy[2*n+1] += lazy[n];
}
lazy[n] = 0;
}
}
void updates(int n, int l, int r, int i, int v) {
if (l == r) {
segs[n] += v;
} else {
int m = (l+r)/2;
if (l <= i && i <= m) {
updates(2*n, l, m, i, v);
} else {
updates(2*n+1, m+1, r, i, v);
}
segs[n] = segs[2*n] + segs[2*n+1];
}
}
void updatem(int n, int l, int r, int a, int b, int v) {
lazypropagate(n, l, r);
if (b < l || r < a) {
return;
} else if (a <= l && r <= b) {
lazy[n] += v;
lazypropagate(n, l, r);
} else {
int m = (l+r)/2;
updatem(2*n, l, m, a, b, v);
updatem(2*n+1, m+1, r, a, b, v);
segmn[n] = min(segmn[2*n], segmn[2*n+1]);
segmx[n] = max(segmx[2*n], segmx[2*n+1]);
}
}
int querys(int n, int l, int r, int a, int b) {
if (b < l || r < a) {
return 0;
} else if (a <= l && r <= b) {
return segs[n];
} else {
int m = (l+r)/2;
return querys(2*n, l, m, a, b) + querys(2*n+1, m+1, r, a, b);
}
}
int querymn(int n, int l, int r, int a, int b) {
if (b < l || r < a) {
return INT_MAX;
}
lazypropagate(n, l, r);
if (a <= l && r <= b) {
return segmn[n];
} else {
int m = (l+r)/2;
return min(querymn(2*n, l, m, a, b), querymn(2*n+1, m+1, r, a, b));
}
}
int querymx(int n, int l, int r, int a, int b) {
if (b < l || r < a) {
return INT_MIN;
}
lazypropagate(n, l, r);
if (a <= l && r <= b) {
return segmx[n];
} else {
int m = (l+r)/2;
return max(querymx(2*n, l, m, a, b), querymx(2*n+1, m+1, r, a, b));
}
}
int trav(int q, int c, vector<int32_t> &v) {
int l = 0, r = q-1;
while(l < r) {
int m = (l+r+1)/2;
if (querymx(1, 0, q-1, m, q-1)-querymn(1, 0, q-1, m, q-1) >= c) {
l = m;
} else {
r = m-1;
}
}
if (querymx(1, 0, q-1, l, q-1)-querymn(1, 0, q-1, l, q-1) >= c) {
return l+1;
} else {
return -1;
}
}
vector<int32_t> distribute_candies(vector<int32_t> c, vector<int32_t> l, vector<int32_t> r, vector<int32_t> v) {
int n = c.size(), q = l.size();
vector<int32_t> ans(n);
for (int i = 0; i < q; i++) {
updatem(1, 0, q-1, i, q-1, v[i]);
updates(1, 0, q-1, i, v[i]);
}
//for (int i = 0; i < q; i++) {
// cout << querymn(1, 0, q-1, i, i) << " ";
//}
//cout << endl;
//for (int i = 0; i < q; i++) {
// cout << i << " " << querymx(1, 0, q-1, i, q-1)-querymn(1, 0, q-1, i, q-1) << endl;
//}
for (int i = 0; i < n; i++) {
int ind = trav(q, c[i], v);
if (ind == -1) {
ans[i] = segs[1];
continue;
}
if (v[ind] < 0) {
ans[i] = 0;
for (int j = ind; j < q; j++) {
ans[i] += v[j];
ans[i] = min(ans[i], c[i]);
ans[i] = max(ans[i], 0);
}
} else {
ans[i] = c[i];
for (int j = ind; j < q; j++) {
ans[i] += v[j];
ans[i] = min(ans[i], c[i]);
ans[i] = max(ans[i], 0);
}
}
ans[i] = min(ans[i], c[i]);
ans[i] = max(ans[i], 0);
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6488 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
6492 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
816 ms |
30036 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 2 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 3 |
Incorrect |
110 ms |
27728 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6488 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
6492 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
