#include "candies.h"
#include<bits/stdc++.h>
using namespace std;
typedef int64_t i64;
#define VII vector<int>
struct seg{
vector<i64>mx,mn,cmx,cmn,op;
int sz = 1;
void build(int x,int lx,int rx){
if(rx-lx == 1){
cmx[x] = cmn[x] = 1;
return;
}
int m = (lx+rx)/2;
build(x*2+1,lx,m);
build(x*2+2,m,rx);
cmx[x] = cmx[x*2+1] + cmx[x*2+2];
cmn[x] = cmn[x*2+1] + cmn[x*2+2];
}
seg(int n){
while(sz < n) sz*=2;
op.assign(sz*2,0ll);
mx.assign(sz*2,0ll);
mn.assign(sz*2,0ll);
cmx.assign(sz*2,0ll);
cmn.assign(sz*2,0ll);
build(0,0,sz);
}
void push(int x,int lx,int rx){
if(rx-lx == 1) return;
op[x*2+1] += op[x];
op[x*2+2] += op[x];
int m = (lx+rx)/2;
NQF(x*2+1,lx,m);
NQF(x*2+2,m,rx);
op[x] = 0;
}
void NQF(int x,int lx,int rx){
if(rx-lx == 1){
cmx[x] = cmn[x] = 1;
mn[x] = mx[x] = op[x];
return;
}
mx[x] = max(mx[x*2+1],mx[x*2+2]) + op[x];
mn[x] = min(mn[x*2+1],mn[x*2+2]) + op[x];
if(mx[x*2+1] > mx[x*2+2]) cmx[x] = cmx[x*2+1];
else if(mx[x*2+2] > mx[x*2+1]) cmx[x] = cmx[x*2+2];
else cmx[x] = cmx[x*2+1] + cmx[x*2+2];
if(mn[x*2+1] < mn[x*2+2]) cmn[x] = cmn[x*2+1];
else if(mn[x*2+2] < mn[x*2+1]) cmn[x] = cmn[x*2+2];
else cmn[x] = cmn[x*2+1] + cmn[x*2+2];
}
void update(int l,int r,int v,int x=0,int lx=0,int rx=-1){
if(rx == -1) rx = sz;
if(rx <= l || lx >= r) return;
NQF(x,lx,rx);
push(x,lx,rx);
if(rx <= r && lx >= l){
mn[x] += v;
mx[x] += v;
op[x] += v;
return;
}
int m = (lx+rx)/2;
update(l,r,v,x*2+1,lx,m);
update(l,r,v,x*2+2,m,rx);
NQF(x,lx,rx);
push(x,lx,rx);
}
void checkMAX(int v,int x=0,int lx=0,int rx=-1){
if(rx == -1) rx = sz;
NQF(x,lx,rx);
push(x,lx,rx);
if(mx[x] > v){
if(cmx[x] == (rx-lx)){
op[x] -= mx[x]-v;
}else{
int m = (lx+rx)/2;
checkMAX(v,x*2+1,lx,m);
checkMAX(v,x*2+2,m,rx);
}
}
NQF(x,lx,rx);
push(x,lx,rx);
}
void checkMIN(int x=0,int lx=0,int rx=-1){
if(rx == -1) rx = sz;
NQF(x,lx,rx);
push(x,lx,rx);
if(mn[x] < 0){
if(cmx[x] == rx-lx){
op[x] -= mn[x];
push(x,lx,rx);
}else{
int m = (lx+rx)/2;
checkMIN(x*2+1,lx,m);
checkMIN(x*2+2,m,rx);
}
}
NQF(x,lx,rx);
push(x,lx,rx);
}
int get(int i,int x=0,int lx=0,int rx=-1){
if(rx == -1) rx = sz;
if(rx-lx == 1) return op[x];
NQF(x,lx,rx);
push(x,lx,rx);
int m = (lx+rx)/2;
if(i < m) return op[x] + get(i,x*2+1,lx,m);
else return op[x] + get(i,x*2+2,m,rx);
}
};
VII distribute_candies(VII c,VII l ,VII r,VII v) {
int n = c.size();
int q = l.size();
seg st(n+1);
for(int i = 0; i < q; i++){
st.update(l[i],r[i]+1,v[i]);
if(v[i] > 0){
st.checkMAX(c[0]);
}else{
st.checkMIN();
}
}
vector<int>ans;
for(int i = 0; i < n; i++) ans.push_back(st.get(i));
return ans;
}
// int main(){
// int n,q; cin >> n >> q;
// vector<int>l(q),r(q),v(q),c(n);
// for(int i = 0; i < n; i++) cin >> c[i];
// for(int i = 0; i < q; i++){
// cin >> l[i] >> r[i] >> v[i];
// }
// vector<int>ans = distribute_candies(c,l,r,v);
// for(int x : ans){
// cout << x << ' ';
// }
// }
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1425 ms |
28388 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
600 KB |
Output is correct |
| 2 |
Correct |
375 ms |
7296 KB |
Output is correct |
| 3 |
Correct |
146 ms |
25288 KB |
Output is correct |
| 4 |
Correct |
994 ms |
31920 KB |
Output is correct |
| 5 |
Correct |
1259 ms |
31972 KB |
Output is correct |
| 6 |
Correct |
1940 ms |
32228 KB |
Output is correct |
| 7 |
Correct |
1644 ms |
31716 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
