#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 200;
const ll inf = 1e18;
ll Time[4 * N], maxPref[4 * N], minPref[4 * N], push[4 * N], pref[4 * N];
vector<int> vx;
int q;
void makepush(int v, int tl, int tr){
if(tl == tr || !push[v])
return;
maxPref[v * 2] += push[v];
minPref[v * 2] += push[v];
push[v * 2] += push[v];
pref[v * 2] += push[v];
maxPref[v * 2 + 1] += push[v];
minPref[v * 2 + 1] += push[v];
push[v * 2 + 1] += push[v];
pref[v * 2 + 1] += push[v];
push[v] = 0;
}
void upd(int v, int tl, int tr, int l, int r, ll x){
if(l > r)
return;
if(tl == l && tr == r){
maxPref[v] += x;
minPref[v] += x;
pref[v] += x;
push[v] += x;
return;
}
makepush(v, tl, tr);
int tm = (tl + tr) / 2;
upd(v * 2, tl, tm, l, min(r, tm), x);
upd(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r, x);
maxPref[v] = max(maxPref[v * 2], maxPref[v * 2 + 1]);
minPref[v] = min(minPref[v * 2], minPref[v * 2 + 1]);
}
void updTime(int v, int tl, int tr, int pos, ll x){
if(tl == tr){
Time[v] += x;
return;
}
int tm = (tl + tr) / 2;
if(pos <= tm)
updTime(v * 2, tl, tm, pos, x);
else
updTime(v * 2 + 1, tm + 1, tr, pos, x);
Time[v] = Time[v * 2] + Time[v * 2 + 1];
}
ll getPref(int v, int tl, int tr, int pos){
if(pos < 0) return 0;
makepush(v, tl, tr);
if(tl == tr){
return pref[v];
}
int tm = (tl + tr) / 2;
if(pos <= tm)
return getPref(v * 2, tl, tm, pos);
else
return getPref(v * 2 + 1, tm + 1, tr, pos);
}
ll Max(int v, int tl, int tr, ll T){ // [T, +oo)
makepush(v, tl, tr);
if(Time[v] < T)
return -inf;
if(!T)
return maxPref[v];
if(tl == tr){
if(Time[v] < T)
return -inf;
return getPref(1, 0, q - 1, tl - 1) + max((vx[tl] > 0 ? +1ll : -1ll) * T, (vx[tl] > 0 ? +1ll : -1ll) * Time[v]);
}
int tm = (tl + tr) / 2;
if(Time[v * 2] >= T)
return max(Max(v * 2, tl, tm, T), maxPref[v * 2 + 1]);
else
return Max(v * 2 + 1, tm + 1, tr, T - Time[v * 2]);
}
ll Min(int v, int tl, int tr, ll T){ // [T, +oo)
makepush(v, tl, tr);
if(Time[v] < T)
return -inf;
if(!T)
return minPref[v];
if(tl == tr){
if(Time[v] < T)
return -inf;
return getPref(1, 0, q - 1, tl - 1) + min((vx[tl] > 0 ? +1ll : -1ll) * T, (vx[tl] > 0 ? +1ll : -1ll) * Time[v]);
}
int tm = (tl + tr) / 2;
if(Time[v * 2] >= T)
return min(Min(v * 2, tl, tm, T), minPref[v * 2]);
else
return Min(v * 2 + 1, tm + 1, tr, T - Time[v * 2]);
}
vector<int> distribute_candies(vector<int> c, vector<int> l,
vector<int> r, vector<int> v) {
vx = v;
int n = c.size();
q = l.size();
vector<ll> total(n);
for(int i = 0; i < q; i ++){
total[l[i]] += v[i];
if(r[i] + 1 < n)
total[r[i] + 1] -= v[i];
}
ll bal = 0;
for(int i = 0; i < n; i ++){
bal += total[i];
total[i] = bal;
}
vector<int> Add[n], Remove[n];
for(int i = 0; i < q; i ++){
Add[l[i]].push_back(i);
if(r[i] + 1 < n)
Remove[r[i] + 1].push_back(i);
}
vector<int> result(n);
for(int i = 0; i < n; i ++){
for(int x : Add[i])
upd(1, 0, q - 1, x, q - 1, v[x]),
updTime(1, 0, q - 1, x, abs(v[x]));
for(int x : Remove[i])
upd(1, 0, q - 1, x, q - 1, -v[x]),
updTime(1, 0, q - 1, x, -abs(v[x]));
ll l = 0, r = 1e18;
while(l < r){
ll mid = (l + r) / 2;
if(r - l == 1)
mid = r;
if(Max(1, 0, q - 1, mid) - Min(1, 0, q - 1, mid) >= c[i])
l = mid;
else
r = mid - 1;
}
result[i] = max(0ll, total[i] - Min(1, 0, q - 1, l));
}
return result;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
0 ms |
332 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
460 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3324 ms |
46832 KB |
Output isn't correct |
| 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 |
Incorrect |
0 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
0 ms |
332 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
460 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
