#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define all(x) x.begin(), x.end()
using ll = long long;
#define pi pair<ll,ll>
#define f first
#define s second
#define int long long
const int inf=1e18;
const int sz = 1<<18;
int lazy[4*sz];
int mn[2*sz];
int mx[2*sz];
pi merge(pi a, pi b) {
return {min(a.f,b.f), max(a.s,b.s)};
}
void push(int v) {
mn[v]+=lazy[v];
mx[v]+=lazy[v];
lazy[2*v+1]+=lazy[v];
lazy[2*v+2]+=lazy[v];
lazy[v]=0;
}
void add(int v, int l, int r, int lx, int rx, int x) {
if (lazy[v]) push(v);
if (rx<=l || r<=lx) return;
if (lx<=l && r<=rx) {
lazy[v]+=x;
push(v);
return;
}
int m=(l+r)>>1;
add(2*v+1,l,m,lx,rx,x);
add(2*v+2,m,r,lx,rx,x);
mn[v]=min(mn[2*v+1],mn[2*v+2]);
mx[v]=max(mx[2*v+1],mx[2*v+2]);
}
void add(int l, int r, int x) {
add(0,0,sz,l,r,x);
}
pi query(int v, int l, int r, int lx, int rx) {
if (lazy[v]) push(v);
if (rx<=l || r<=lx) return {inf,-inf};
if (lx<=l && r<=rx) return {mn[v],mx[v]};
int m=(l+r)>>1;
auto lq=query(2*v+1,l,m,lx,rx);
auto rq=query(2*v+2,m,r,lx,rx);
mn[v]=min(mn[2*v+1],mn[2*v+2]);
mx[v]=max(mx[2*v+1],mx[2*v+2]);
return {min(lq.f,rq.f),max(lq.s,rq.s)};
}
pi query(int l, int r) {
return query(0,0,sz,l,r);
}
#undef int
void addqueries(int n, vector<int>&l, vector<int>&r, vector<int>&v) {
reverse(all(l));
reverse(all(r));
reverse(all(v));
forn(i,2) l.pb(0);
forn(i,2) r.pb(n-1);
v.pb(-1e9); v.pb(1e9);
reverse(all(l));
reverse(all(r));
reverse(all(v));
}
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
int n=c.size(), q=l.size()+2;
addqueries(n,l,r,v);
vector<vector<int>> add(n), del(n);
forn(i,q) add[l[i]].pb(i), del[r[i]].pb(i);
sgt q);
vector<int> ans(n);
forn(i,n) {
for(auto&x:add[i]) add(x,q,v[x]);
int l=0, r=q-1;
while (l<r) {
int mid=(l+r+1)>>1;
auto x = query(mid,q);
if (x.s - x.f < c[i]) r=mid-1;
else l=mid;
}
auto z = query(r,q);
int t=r;
l=r+1, r=q-1;
while (l<r) {
int mid=(l+r)>>1;
auto x=query(t+1,mid+1);
if (x.s!=z.s && x.f!=z.f) l=mid+1;
else r=mid;
}
auto x = query(r,r+1);
auto y = query(q-1,q);
z = query(t,t+1);
if (x.f <= z.f) ans[i]=y.f-x.f;
else ans[i]=c[i]+y.f-x.f;
for(auto&x:del[i]) add(x,q,-v[x]);
}
return ans;
}
Compilation message
candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:83:2: error: 'sgt' was not declared in this scope
83 | sgt q);
| ^~~
candies.cpp:86:34: error: no match for call to '(std::vector<std::vector<int> >) (int&, int&, __gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type&)'
86 | for(auto&x:add[i]) add(x,q,v[x]);
| ^
candies.cpp:110:35: error: no match for call to '(std::vector<std::vector<int> >) (int&, int&, __gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type)'
110 | for(auto&x:del[i]) add(x,q,-v[x]);
| ^
