#include "candies.h"
#include <bits/stdc++.h>
using std::cin;
using std::cout;
using std::vector;
using std::string;
using ll = long long;
using vi = vector<ll>;
using vii = vector<vi>;
using pii = std::pair<ll,ll>;
using std::endl;
#define rep(i,j,k) for(ll i=ll(j); i<ll(k); i++)
#define REP(i,j,k) for(ll i=ll(j); i<=ll(k); i++)
#define per(i,j,k) for(ll i=ll(j); i>=ll(k); i--)
#define ln "\n"
#define pb emplace_back
#define mp std::make_pair
#define mtp std::make_tuple
#define all(a) a.begin(),a.end()
struct lazy_segment_tree{
ll N;
ll log;
vi sum, max, min;
vi lsum, lmax, lmin;
lazy_segment_tree(ll n){
N = 1;
log = 0;
while(N <= n){
N *= 2;
log++;
}
sum.resize(2*N);
max.resize(2*N);
min.resize(2*N);
lsum.resize(2*N);
lmax.resize(2*N);
lmin.resize(2*N);
}
void update(ll a, ll b, ll val){
ll l = a+N, r = b+N-1;
per(i,log,0){
eval(l>>i);
eval(r>>i);
}
while(l < r){
if(l & 1){
lmax[l] = std::max(lmax[l], lsum[l]+val);
lmin[l] = std::min(lmin[l], lsum[l]+val);
lsum[l] += val;
l++;
}
l >>= 1;
if((r&1) == 0){
lmax[r] = std::max(lmax[r], lsum[r]+val);
lmin[r] = std::min(lmin[r], lsum[r]+val);
lsum[r] += val;
r--;
}
r >>= 1;
}
if(l == r){
lmax[l] = std::max(lmax[l], lsum[l]+val);
lmin[l] = std::min(lmin[l], lsum[l]+val);
lsum[l] += val;
}
}
/*void update(ll a, ll b, ll val, ll now = 1, ll l = 0, ll r = -1){
if(r == -1) r = N;
if(r <= a || b <= l) return;
eval(now);
if(a <= l && r <= b){
if(val > 0) lmax[now] = val;
else lmin[now] = val;
lsum[now] += val;
return;
}
update(a,b,val,now*2,l,(l+r)/2);
update(a,b,val,now*2+1,(l+r)/2,r);
}*/
pii calc(ll now){
now += N;
per(i,log,0){
eval(now>>i);
}
return mp(max[now], min[now]);
}
void eval(ll now){
/*if(lmax[now]){
max[now] = std::max(max[now], sum[now]+lmax[now]);
if(now < N){
lmax[now*2] = std::max(lmax[now*2], lsum[now*2]+lmax[now]);
lmax[now*2+1] = std::max(lmax[now*2+1], lsum[now*2+1]+lmax[now]);
}
lmax[now] = 0;
}
if(lmin[now]){
min[now] = std::min(min[now], sum[now]+lmin[now]);
if(now < N){
lmin[now*2] = std::min(lmin[now*2], lsum[now*2]+lmin[now]);
lmin[now*2+1] = std::min(lmin[now*2+1], lsum[now*2+1]+lmin[now]);
}
lmin[now] = 0;
}
if(lsum[now]){
sum[now] += lsum[now];
if(now < N){
lsum[now*2] += lsum[now];
lsum[now*2+1] += lsum[now];
}
lsum[now] = 0;
}
lmax[now] = lmin[now] = lsum[now] = 0;
*/
max[now] = std::max(max[now], sum[now]+lmax[now]);
min[now] = std::min(min[now], sum[now]+lmin[now]);
sum[now] += lsum[now];
if(now < N){
lmax[now*2] = std::max(lmax[now*2], lsum[now*2]+lmax[now]);
lmin[now*2] = std::min(lmin[now*2], lsum[now*2]+lmin[now]);
lsum[now*2] += lsum[now];
lmax[now*2+1] = std::max(lmax[now*2+1], lsum[now*2+1]+lmax[now]);
lmin[now*2+1] = std::min(lmin[now*2+1], lsum[now*2+1]+lmin[now]);
lsum[now*2+1] += lsum[now];
}
lmax[now] = lmin[now] = lsum[now] = 0;
}
};
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
std::vector<int> r, std::vector<int> v) {
int N = c.size();
ll Q = l.size();
vi left(N,-1), right(N,Q);
while(true){
lazy_segment_tree seg(N);
vi mid(N);
bool flg = true;
vii query(Q+1);
rep(i,0,N){
if(left[i]+1 < right[i]){
mid[i] = (left[i]+right[i])/2;
query[mid[i]].pb(i);
flg = false;
}
}
if(flg) break;
per(i,Q,0){
if(i < Q){
seg.update(l[i], r[i]+1, v[i]);
}
for(auto el: query[i]){
auto ret = seg.calc(el);
if(c[el] <= ret.first-ret.second) left[el] = mid[el];
else right[el] = mid[el];
}
}
}
vector<int> ans(N);
{
vii max(Q+1), min(Q+1);
rep(i,0,N){
if(left[i] == -1) max[0].pb(i);
else{
if(v[left[i]] > 0){
min[left[i]].pb(i);
}
else{
max[left[i]].pb(i);
}
}
}
lazy_segment_tree seg(N);
per(i,Q,0){
if(i < Q){
seg.update(l[i], r[i]+1, v[i]);
}
for(auto el: max[i]){
ans[el] = seg.calc(el).first;
}
for(auto el: min[i]){
ans[el] = c[el]+seg.calc(el).second;
}
}
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
3 ms |
340 KB |
Output is correct |
| 4 |
Correct |
4 ms |
340 KB |
Output is correct |
| 5 |
Correct |
10 ms |
720 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5053 ms |
49892 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1114 ms |
14592 KB |
Output is correct |
| 3 |
Correct |
614 ms |
34924 KB |
Output is correct |
| 4 |
Correct |
4937 ms |
48920 KB |
Output is correct |
| 5 |
Execution timed out |
5049 ms |
50840 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
829 ms |
14604 KB |
Output is correct |
| 4 |
Correct |
593 ms |
35368 KB |
Output is correct |
| 5 |
Correct |
2955 ms |
49368 KB |
Output is correct |
| 6 |
Correct |
2761 ms |
49256 KB |
Output is correct |
| 7 |
Correct |
2751 ms |
48876 KB |
Output is correct |
| 8 |
Correct |
2954 ms |
49364 KB |
Output is correct |
| 9 |
Correct |
3242 ms |
48344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
3 ms |
340 KB |
Output is correct |
| 4 |
Correct |
4 ms |
340 KB |
Output is correct |
| 5 |
Correct |
10 ms |
720 KB |
Output is correct |
| 6 |
Execution timed out |
5053 ms |
49892 KB |
Time limit exceeded |
| 7 |
Halted |
0 ms |
0 KB |
- |
