#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;
}
};
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 |
436 KB |
Output is correct |
| 4 |
Correct |
5 ms |
468 KB |
Output is correct |
| 5 |
Correct |
10 ms |
724 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3715 ms |
54820 KB |
Output is correct |
| 2 |
Correct |
3985 ms |
52624 KB |
Output is correct |
| 3 |
Correct |
3730 ms |
52876 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
428 KB |
Output is correct |
| 2 |
Correct |
1119 ms |
16644 KB |
Output is correct |
| 3 |
Correct |
414 ms |
37008 KB |
Output is correct |
| 4 |
Correct |
4657 ms |
50772 KB |
Output is correct |
| 5 |
Correct |
4358 ms |
57144 KB |
Output is correct |
| 6 |
Correct |
4850 ms |
55524 KB |
Output is correct |
| 7 |
Execution timed out |
5021 ms |
54772 KB |
Time limit exceeded |
| 8 |
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 |
569 ms |
17236 KB |
Output is correct |
| 4 |
Correct |
408 ms |
36652 KB |
Output is correct |
| 5 |
Correct |
2764 ms |
52912 KB |
Output is correct |
| 6 |
Correct |
2050 ms |
53416 KB |
Output is correct |
| 7 |
Correct |
2043 ms |
53004 KB |
Output is correct |
| 8 |
Correct |
2140 ms |
52736 KB |
Output is correct |
| 9 |
Correct |
1900 ms |
52348 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 |
436 KB |
Output is correct |
| 4 |
Correct |
5 ms |
468 KB |
Output is correct |
| 5 |
Correct |
10 ms |
724 KB |
Output is correct |
| 6 |
Correct |
3715 ms |
54820 KB |
Output is correct |
| 7 |
Correct |
3985 ms |
52624 KB |
Output is correct |
| 8 |
Correct |
3730 ms |
52876 KB |
Output is correct |
| 9 |
Correct |
1 ms |
428 KB |
Output is correct |
| 10 |
Correct |
1119 ms |
16644 KB |
Output is correct |
| 11 |
Correct |
414 ms |
37008 KB |
Output is correct |
| 12 |
Correct |
4657 ms |
50772 KB |
Output is correct |
| 13 |
Correct |
4358 ms |
57144 KB |
Output is correct |
| 14 |
Correct |
4850 ms |
55524 KB |
Output is correct |
| 15 |
Execution timed out |
5021 ms |
54772 KB |
Time limit exceeded |
| 16 |
Halted |
0 ms |
0 KB |
- |
