#include "candies.h"
#include <bits/stdc++.h>
using std::cin;
using std::cout;
using std::vector;
using std::string;
using ll = int;
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()
constexpr ll inf = (1<<30);
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 now = 1, ll l = 0, ll r = -1){
if(r == -1) r = N;
eval(now);
if(a <= l && r <= b){
if(val > 0) lmax[now] = val;
else lmin[now] = val;
lsum[now] += val;
return;
}
if(r <= a || b <= l) 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+1,0){
eval((now>>i));
}
return mp(max[now], min[now]);
}
void eval(ll now){
max[now] = std::min(inf,std::max(max[now], sum[now]+lmax[now]));
min[now] = std::max(-inf,std::min(min[now], sum[now]+lmin[now]));
sum[now] += lsum[now];
sum[now] = std::min(inf, sum[now]);
sum[now] = std::max(sum[now], -inf);
if(now < N){
lmax[now*2] = std::min(inf,std::max(lmax[now*2], lsum[now*2]+lmax[now]));
lmin[now*2] = std::max(-inf,std::min(lmin[now*2], lsum[now*2]+lmin[now]));
lsum[now*2] += lsum[now];
lsum[now*2] = std::min(lsum[now*2], inf);
lsum[now*2] = std::max(lsum[now*2+1], -inf);
lmax[now*2+1] = std::min(inf,std::max(lmax[now*2+1], lsum[now*2+1]+lmax[now]));
lmin[now*2+1] = std::max(-inf,std::min(lmin[now*2+1], lsum[now*2+1]+lmin[now]));
lsum[now*2+1] += lsum[now];
lsum[now*2+1] = std::min(lsum[now*2], inf);
lsum[now*2+1] = std::max(lsum[now*2+1], -inf);
}
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 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5044 ms |
27736 KB |
Time limit exceeded |
| 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 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
