#include "candies.h"
#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;
int n, q;
const int MAX = 2e5 + 5;
int tree[4 * MAX];
array<int, 3> lazy[4 * MAX];
pii arr[MAX];
void match(int node, int ch){
lazy[ch][0] += lazy[node][0];
if(lazy[node][1] || lazy[node][2]){
lazy[ch] = lazy[node];
}
}
void relax(int node, int l, int r){
if(!lazy[node][0] && !lazy[node][1] && !lazy[node][2]) return;
if(lazy[node][1]) tree[node] = 0;
if(lazy[node][2]) tree[node] = arr[r].first;
tree[node] += lazy[node][0];
if(l == r){
lazy[node] = {0, 0, 0};
return;
}
match(node, 2 * node);
match(node, 2 * node + 1);
lazy[node] = {0, 0, 0};
}
void update(int node, int l, int r, int ul, int ur, int v, int t){
relax(node, l, r);
if(ur < l || r < ul){
return;
}
if(ul <= l && r <= ur){
if(t == 1){
lazy[node][0] += v;
}
if(t == 2){
lazy[node] = {0, 1, 0};
}
if(t == 3){
lazy[node] = {0, 0, 1};
}
relax(node, l, r);
return;
}
int mid = (l + r) / 2;
update(2 * node, l, mid, ul, ur, v, t);
update(2 * node + 1, mid + 1, r, ul, ur, v, t);
tree[node] = max(tree[2 * node], tree[2 * node + 1]);
}
int get(int node, int l, int r, int pos){
relax(node, l, r);
if(l == r){
return tree[node];
}
int mid = (l + r) / 2;
if(pos <= mid){
return get(2 * node, l, mid, pos);
}
else{
return get(2 * node + 1, mid + 1, r, pos);
}
}
int f(int val, bool b){
int l = 1, r = n, node = 1;
if(tree[node] <= val && !b){
return n + 1;
}
if(arr[r].first - tree[node] <= val && b){
return n + 1;
}
while(l < r){
int mid = (l + r) / 2;
relax(2 * node, l, mid);
if(b){
if(arr[mid].first - tree[2 * node] > val){
r = mid;
node = node * 2;
}
else{
l = mid + 1;
node = node * 2 + 1;
}
}
else{
if(tree[2 * node] > val){
r = mid;
node = node * 2;
}
else{
l = mid + 1;
node = node * 2 + 1;
}
}
}
return l;
}
vector<int> distribute_candies(vector<int> c, vector<int> l,
vector<int> r, vector<int> v) {
n = c.size(), q = l.size();
for(int i = 1; i <= n; i++){
arr[i] = {c[i - 1], i - 1};
}
sort(arr + 1, arr + n + 1);
for(int i = 0; i < q; i++){
if(v[i] < 0){
int pos = f(-v[i], 0);
update(1, 1, n, 1, pos - 1, 0, 2);
if(pos != n + 1){
update(1, 1, n, pos, n, v[i], 1);
}
}
else{
int pos = f(v[i], 1);
update(1, 1, n, 1, pos - 1, 0, 3);
if(pos != n + 1){
update(1, 1, n, pos, n, v[i], 1);
}
}
}
vector<int> ans(n);
for(int i = 1; i <= n; i++){
ans[arr[i].second] = get(1, 1, n, i);
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
134 ms |
22100 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
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 |
348 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
