#include "candies.h"
#include <cassert>
#include <cstdio>
#include <vector>
#include <bits/stdc++.h>
using namespace std;
#define maxn 200200
#define mid ((ini+fim)/2)
#define pb push_back
#define ll long long
#define search iwfew
#define debug printf
ll T[4*maxn];
ll mn[4*maxn];
ll mx[4*maxn];
int pos_mn[4*maxn];
ll lazy[4*maxn];
int n,q;
void refresh(int ini,int fim,int p){
if(ini < fim){
lazy[2*p] += lazy[p];
lazy[2*p+1] += lazy[p];
}
mn[p] += lazy[p];
mx[p] += lazy[p];
lazy[p] = 0;
}
void merge(int ini,int fim,int p){
mx[p] = max(mx[2*p],mx[2*p+1]);
mn[p] = min(mn[2*p],mn[2*p+1]);
pos_mn[p] = pos_mn[2*p];
if(mn[2*p+1] < mn[2*p]) pos_mn[p] = pos_mn[2*p+1];
T[p] = mx[p] - mn[p];
}
void bd(int ini,int fim,int p){
if(ini == fim){
pos_mn[p] = ini;
return;
}
bd(ini,mid,2*p);
bd(mid+1,fim,2*p+1);
pos_mn[p] = ini;
}
int search(int ini,int fim,int p,ll d,ll mnr=0,ll mxr=0,ll hasr=0){
refresh(ini,fim,p);
if(ini == fim) return ini;
ll gapR = T[2*p+1];
if(hasr) gapR = max(gapR, mxr - mn[2*p+1]);
if(hasr) gapR = max(gapR, mx[2*p+1] - mnr);
if(gapR > d) return search(mid+1,fim,2*p+1,d,mnr,mxr,hasr);
ll mn_ = mn[2*p+1]; if(hasr) mn_ = min(mn_, mnr);
ll mx_ = mx[2*p+1]; if(hasr) mx_ = max(mx_, mxr);
return search(ini,mid,2*p,d,mn_,mx_,1);
}
ll get(int ini,int fim,int p,int pos){
refresh(ini,fim,p);
if(ini > pos || fim < pos) return 0;
if(ini == fim) return mx[p];
ll ret = get(ini,mid,2*p,pos) + get(mid+1,fim,2*p+1,pos);
merge(ini,fim,p);
return ret;
}
void upd(int ini,int fim,int p,int l,int r,int x){
refresh(ini,fim,p);
if(l > fim || r < ini) return;
if(ini >= l && fim <= r){
lazy[p] += x;
refresh(ini,fim,p);
return;
}
upd(ini,mid,2*p,l,r,x);
upd(mid+1,fim,2*p+1,l,r,x);
merge(ini,fim,p);
}
vector<int> Ti[4*maxn];
void updi(int ini,int fim,int p,int a,int b,int k){
if(ini > b) return;
if(fim < a) return;
if(ini >= a && fim <= b){
Ti[p].pb(k);
return;
}
updi(ini,mid,2*p,a,b,k);
updi(mid+1,fim,2*p+1,a,b,k);
}
vector<int> ans;
vector<int> l,r,add,cap;
void go(int ini,int fim,int p){
debug("go %d~%d\n",ini,fim);
for(int a : Ti[p]){
upd(0,q,1,a+1,q,add[a]);
debug("add %d at %d\n",add[a],a);
}
if(ini == fim){
int c = cap[ini];
int beg = 0;
debug("qry %d cap %d\n",ini,c);
//if(T[1] > c)
//beg = 1 + search(0,q,1,c);
beg = max(beg,pos_mn[1]);
ll //delta = get(0,q,1,q) - get(0,q,1,beg);
delta = get(0,q,1,q);
ans[ini] = min((ll)c,delta);
debug("get %d = %lld\n",q,get(0,q,1,q));
debug("get %d = %lld\n",beg-1,get(0,q,1,beg-1));
debug("get %d = %lld\n",beg,get(0,q,1,beg));
debug("T[1] = %d, beg = %d, delta = %lld\n\n",T[1],beg,delta);
/*if(beg > 0){
if(get(0,q,1,beg-1) < get(0,q,1,beg)) ans[ini] = c;
}
if(delta >= 0) ans[ini] = min(ans[ini]+delta,c);
else ans[ini] = max(ans[ini]+delta,0);
*/
// if(delta == 0 && beg > 0 && get(0,q,1,beg-1) > get(0,q,1,beg)) ans[ini] = 0;
}
if(ini < fim) go(ini,mid,2*p);
if(ini < fim) go(mid+1,fim,2*p+1);
for(int a : Ti[p]){
upd(0,q,1,a+1,q,-add[a]);
debug("rem %d at %d\n",add[a],a);
}
}
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> L,
std::vector<int> R, std::vector<int> v) {
n = c.size();
q = L.size();
cap = c;
l = L;
r = R;
add = v;
for(int i=0;i<q;i++)
updi(0,n-1,1,l[i],r[i],i);
bd(0,q-1,1);
for(int i=0;i<n;i++) ans.pb(0);
go(0,n-1,1);
return ans;
}
Compilation message
candies.cpp: In function 'void go(int, int, int)':
candies.cpp:157:18: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
157 | debug("T[1] = %d, beg = %d, delta = %lld\n\n",T[1],beg,delta);
| ~^ ~~~~
| | |
| int long long int
| %lld
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
19024 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4742 ms |
219644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
19276 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
19020 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
19024 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
