#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];
int pos_mx[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];
pos_mx[p] = pos_mx[2*p];
if(mx[2*p+1] > mx[2*p]) pos_mx[p] = pos_mx[2*p+1];
T[p] = mx[p] - mn[p];
debug("pos_mx[%d] := %d\n",p,pos_mx[p]);
}
void bd(int ini,int fim,int p){
if(ini == fim){
pos_mn[p] = ini;
pos_mx[p] = ini;
return;
}
bd(ini,mid,2*p);
bd(mid+1,fim,2*p+1);
pos_mn[p] = ini;
pos_mx[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;
refresh(mid+1,fim,2*p+1);
merge(ini,fim,p);
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 vm, vM;
int pm, pM;
void qr(int ini,int fim,int p,int l,int r){
debug("qr %d~%d p %d\n",ini,fim,p);
refresh(ini,fim,p);
if(ini > r || fim < l) return;
if(ini >= l && fim <= r){
if(mn[p] < vm){
vm = mn[p];
pm = pos_mn[p];
}
debug("mx %lld po %d\n",mx[p],pos_mx[p]);
if(mx[p] > vM){
vM = mx[p];
pM = pos_mx[p];
}
return;
}
qr(ini,mid,2*p,l,r);
qr(mid+1,fim,2*p+1,l,r);
merge(ini,fim,p);
}
int get_min(int a){
vm = 1e18;
vM = -1e18;
qr(0,q,1,a,q);
return pm;
}
int get_max(int a){
vm = 1e18;
vM = -1e18;
qr(0,q,1,a,q);
debug("mx (%d) = %d\n",a,pM);
return pM;
}
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){
ll 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);
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)) {
beg = get_min(beg);
delta = get(0,q,1,q) - get(0,q,1,beg);
ans[ini] = delta;
}
else {
beg = get_max(beg);
delta = get(0,q,1,q) - get(0,q,1,beg);
ans[ini] = c + delta;
}
}
else ans[ini] = delta;
// 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);
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:195:22: warning: format '%d' expects argument of type 'int', but argument 3 has type 'long long int' [-Wformat=]
195 | debug("qry %d cap %d\n",ini,c);
| ~^ ~
| | |
| int long long int
| %lld
candies.cpp:208:18: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
208 | 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 |
9 ms |
19148 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5028 ms |
568528 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
19788 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
19040 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
19148 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
