#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) {
int l = 0, r = q;
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;
} 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 = 1; i <= q; i++) {
updatem(1, 0, q, i, q, v[i-1]);
updates(1, 0, q, i, v[i-1]);
}
for (int i = 0; i < n; i++) {
int ind = trav(q, c[i]);
if (ind == -1) {
ans[i] = segs[1] - querymn(1, 0, q, 0, q);
continue;
}
int tmp2 = segs[1], tmp1 = querys(1, 0, q, 0, ind);
//cout << tmp1 << " " << tmp2;
if (tmp1 < tmp2) {
int tmp3 = querymx(1, 0, q, ind, q);
//cout << " " << tmp3 << endl;
ans[i] = c[i] - (tmp3-tmp2);
} else {
int tmp3 = querymn(1, 0, q, ind, q);
//cout << " " << tmp3 << endl;
ans[i] = tmp2-tmp3;
}
}
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 |
699 ms |
30088 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6488 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 |
Incorrect |
1 ms |
6492 KB |
Output isn't correct |
| 3 |
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 |
- |
