#include <bits/stdc++.h>
#include "candies.h"
using namespace std;
typedef long long ll;
#ifdef LOCAL
#include "../debug.h"
#else
#define debug(...) 123
#endif
const int N = 2e5 + 20;
const ll inf = 1e17;
ll xtime[4 * N], mx[4 * N], mn[4 * N], push[4 * N];
ll u[N];
void makepush(int v){
if(!push[v])
return;
mx[v * 2] += push[v];
mn[v * 2] += push[v];
mx[v * 2 + 1] += push[v];
mn[v * 2 + 1] += push[v];
push[v * 2] += push[v];
push[v * 2 + 1] += push[v];
push[v] = 0;
}
void modify_value(int v, int tl, int tr, int l, int r, int x){
if(l > r)
return;
if(tl == l && tr == r){
mx[v] += x;
mn[v] += x;
push[v] += x;
return;
}
makepush(v);
int tm = (tl + tr) / 2;
modify_value(v * 2, tl, tm, l, min(r, tm), x);
modify_value(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r, x);
mx[v] = max(mx[v * 2], mx[v * 2 + 1]);
mn[v] = min(mn[v * 2], mn[v * 2 + 1]);
}
void modify_time(int v, int tl, int tr, int pos, int x){
if(tl == tr){
xtime[v] += x;
return;
}
int tm = (tl + tr) / 2;
if(pos <= tm)
modify_time(v * 2, tl, tm, pos, x);
else
modify_time(v * 2 + 1, tm + 1, tr, pos, x);
xtime[v] = xtime[v * 2] + xtime[v * 2 + 1];
}
ll getmax(int v, int tl, int tr, ll t){
if(xtime[v] < t){
return -inf;
}
if(!t)
return mx[v];
if(tl == tr){
return mx[v] - u[tl] + (u[tl] > 0 ? xtime[v] : -t);
}
makepush(v);
int tm = (tl + tr) / 2;
if(xtime[v * 2] >= t){
return max(getmax(v * 2, tl, tm, t), mx[v * 2 + 1]);
}else{
return getmax(v * 2 + 1, tm + 1, tr, t - xtime[v * 2]);
}
}
ll getmin(int v, int tl, int tr, ll t){
if(xtime[v] < t){
return inf;
}
if(!t)
return mn[v];
if(tl == tr){
return mn[v] - u[tl] + (u[tl] > 0 ? t : -xtime[v]);
}
makepush(v);
int tm = (tl + tr) / 2;
if(xtime[v * 2] >= t){
return min(getmin(v * 2, tl, tm, t), mn[v * 2 + 1]);
}else{
return getmin(v * 2 + 1, tm + 1, tr, t - xtime[v * 2]);
}
}
vector<int> distribute_candies(vector<int> c, vector<int> lx, vector<int> rx, vector<int> vx) {
int n = c.size();
vector<tuple<int, int, int>> md;
md.emplace_back(0, n - 1, -1e9);
md.emplace_back(0, n - 1, +1e9);
vector<ll> bal(n + 1);
vector<vector<int>> open(n + 1), close(n + 1);
int q = lx.size();
for(int i = 0; i < q; i ++){
md.emplace_back(lx[i], rx[i], vx[i]);
bal[lx[i]] += vx[i];
bal[rx[i]+1] -= vx[i];
}
q = md.size();
for(int i = 0; i < q; i ++){
open[get<0>(md[i])].emplace_back(i);
close[get<1>(md[i]) + 1].emplace_back(i);
}
for(int i = 0; i < q; i ++)
u[i] = get<2>(md[i]);
ll sum = 0;
for(int i = 0; i < n; i ++){
sum += bal[i];
bal[i] = sum;
}
vector<int> ans(n);
for(int i = 0; i < n; i ++){
for(int j : open[i]){
modify_value(1, 0, q - 1, j, q - 1, u[j]);
modify_time(1, 0, q - 1, j, abs(u[j]));
}
for(int j : close[i]){
modify_value(1, 0, q - 1, j, q - 1, -u[j]);
modify_time(1, 0, q - 1, j, -abs(u[j]));
}
ll l = 0, r = inf;
while(l < r){
ll m = (l + r) / 2;
if(getmax(1, 0, q - 1, m) - getmin(1, 0, q - 1, m) > c[i])
l = m + 1;
else
r = m;
}
ans[i] = bal[i] - getmin(1, 0, q - 1, l);
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1645 ms |
50716 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
