#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mk make_pair
#define pb push_back
#define fr first
#define sc second
vector<int> lazy, set_c, set_0;
vector<pii> s_c, seg;
void prop(int node, int l, int r) {
if(set_c[node]) seg[node] = {s_c[l].fr, s_c[r].fr};
if(set_0[node]) seg[node] = {0,0};
seg[node].fr += lazy[node];
seg[node].sc += lazy[node];
if(l != r) {
lazy[2*node] += lazy[node];
lazy[2*node+1] += lazy[node];
if(set_c[node]) {
set_c[2*node] = set_c[2*node+1] = 1;
set_0[2*node] = set_0[2*node+1] = lazy[2*node] = lazy[2*node+1] = 0;
}
if(set_0[node]) {
set_0[2*node] = set_0[2*node+1] = 1;
set_c[2*node] = set_c[2*node+1] = lazy[2*node] = lazy[2*node+1] = 0;
}
}
lazy[node] = set_0[node] = set_c[node] = 0;
}
void update(int node, int l, int r, int p, int q, bool S0, bool SC, int val) {
prop(node, l, r);
if(r < p or q < l) return;
if(p <= l and r <= q) {
set_0[node] = S0;
set_c[node] = SC;
lazy[node] = val;
prop(node, l, r);
return;
}
int mid = (l+r)/2;
update(2*node, l, mid, p, q, S0, SC, val);
update(2*node+1, mid+1, r, p, q, S0, SC, val);
seg[node].fr = seg[2*node].fr;
seg[node].sc = seg[2*node+1].sc;
}
int query_minus(int node, int l, int r, int val) {
prop(node, l, r);
if(seg[node].fr > val) return l-1;
if(l == r) return l;
int mid = (l+r)/2;
prop(2*node, l, mid);
prop(2*node+1, mid+1, r);
if(seg[2*node+1].fr <= val) return query_minus(2*node+1, mid+1, r, val);
else return query_minus(2*node, l, mid, val);
}
int query_plus(int node, int l, int r, int val) {
prop(node, l, r);
if(seg[node].fr + val < s_c[l].fr) return l-1;
if(l == r) return l;
int mid = (l+r)/2;
prop(2*node, l, mid);
prop(2*node+1, mid+1, r);
if(seg[2*node+1].fr + val >= s_c[mid+1].fr) return query_plus(2*node+1, mid+1, r, val);
else return query_plus(2*node, l, mid, val);
}
int query(int node, int l, int r, int ind) {
prop(node, l, r);
if(l == r) return seg[node].fr;
int mid = (l+r)/2;
if(ind <= mid) return query(2*node, l, mid, ind);
else return query(2*node+1, mid+1, r, ind);
}
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
int n = sz(c), q = sz(l);
for(int i = 0; i < n; i++) s_c.pb({c[i], i});
sort(all(s_c));
seg.resize(4*n);
lazy.resize(4*n);
set_0.resize(4*n);
set_c.resize(4*n);
for(int i = 0; i < q; i++) {
if(v[i] > 0) {
int x = query_plus(1, 0, n-1, v[i]);
update(1, 0, n-1, 0, x, 0, 1, 0);
update(1, 0, n-1, x+1, n-1, 0, 0, v[i]);
}
else {
int x = query_minus(1, 0, n-1, -v[i]);
update(1, 0, n-1, 0, x, 1, 0, 0);
update(1, 0, n-1, x+1, n-1, 0, 0, v[i]);
}
//for(int i = 0; i < n; i++) cout << query(1, 0, n-1, i) << " \n"[i==n-1];
}
vector<int> ans(n);
for(int i = 0; i < n; i++) ans[s_c[i].sc] = query(1, 0, n-1, i);
return ans;
}
/*
5
3 5 10 11 15
3
0 4 5
0 4 -2
0 4 6
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
267 ms |
29380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
