#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define ll long long
const int mxN = 2e5 + 7;
const int SZ = exp2(ceil(log2(mxN)));
const ll INF = 1e18;
int n, q;
ll lazy[4*mxN];
pair<ll,int> seg[4*mxN][2];
vector<pair<int,int>> que[mxN][2];
void push(int ind, int l, int r, int cnt = 1) {
seg[ind][0].f += lazy[ind];
seg[ind][1].f += lazy[ind];
if (l != r) {
lazy[2*ind] += lazy[ind];
lazy[2*ind+1] += lazy[ind];
if (cnt) {
int mid = (l+r)/2;
push(2*ind,l,mid,cnt-1);
push(2*ind+1,mid+1,r,cnt-1);
}
}
lazy[ind] = 0;
}
void update(int lo, int hi, ll inc, int ind=1, int l=0, int r=SZ-1) {
push(ind,l,r);
if (lo > r || l > hi) {
return;
}
if (lo <= l && r <= hi) {
lazy[ind] += inc;
push(ind,l,r);
return;
}
int mid = (l+r)/2;
update(lo,hi,inc,2*ind,l,mid);
update(lo,hi,inc,2*ind+1,mid+1,r);
if (seg[2*ind][0].f < seg[2*ind+1][0].f) seg[ind][0] = seg[2*ind][0];
else seg[ind][0] = seg[2*ind+1][0];
if (seg[2*ind][1].f > seg[2*ind+1][1].f) seg[ind][1] = seg[2*ind][1];
else seg[ind][1] = seg[2*ind+1][1];
}
// {min, max}
pair<pair<ll,int>,pair<ll,int>>
walk(int c, pair<ll,int> mn, pair<ll,int> mx, int ind=1, int l=0, int r=SZ-1) {
push(ind,l,r);
if (l == r) {
return {min(mn,seg[ind][0]),max(mx,seg[ind][1])};
}
int mid = (l+r)/2;
if (max(mx.f,seg[2*ind+1][1].f) - min(mn.f,seg[2*ind+1][0].f) >= c) {
return walk(c,mn,mx,2*ind+1,mid+1,r);
}
else {
return walk(c,min(mn,seg[2*ind+1][0]),max(mx,seg[2*ind+1][1]),
2*ind,l,mid);
}
}
ll query(int pos, int ind=1, int l=0, int r=SZ-1) {
push(ind,l,r);
if (l == r) {
return seg[ind][0].f;
}
int mid = (l+r)/2;
if (pos <= mid) {
return query(pos,2*ind,l,mid);
}
else {
return query(pos,2*ind+1,mid+1,r);
}
}
vector<int> distribute_candies(vector<int> c, vector<int> l,
vector<int> r, vector<int> v) {
n = c.size(), q = v.size()+1;
seg[1+SZ][0] = seg[1+SZ][1] = {0, 1};
for (int i = 2; i <= q; ++i) {
que[l[i-2]][0].push_back({v[i-2], i});
que[r[i-2]][1].push_back({v[i-2], i});
seg[i+SZ][0] = seg[i+SZ][1] = {0, i};
}
for (int ind = SZ-1; ind >= 0; --ind) {
if (seg[2*ind][0].f < seg[2*ind+1][0].f) seg[ind][0] = seg[2*ind][0];
else seg[ind][0] = seg[2*ind+1][0];
if (seg[2*ind][1].f > seg[2*ind+1][1].f) seg[ind][1] = seg[2*ind][1];
else seg[ind][1] = seg[2*ind+1][1];
}
vector<int> ans(n);
for (int i = 0; i < n; ++i) {
for (auto [val, t] : que[i][0]) {
update(t, q, val);
}
update(1,q,-c[i]);
/*
for (int j = 0; j <= q; ++j) {
cout << query(j,j).f.f << ' ';
}
cout << "\n";
*/
auto cur = walk(c[i],{INF,0},{-INF,0});
if (cur.s.s > cur.f.s) {
ans[i] = c[i] + query(q) - query(cur.s.s);
}
else {
ans[i] = query(q) - query(cur.f.s);
}
/*
int lb = 0, rb = q;
ll res = 0;
while (lb <= rb) {
int mb = (lb+rb)/2;
auto cur = query(mb,q);
if (cur.s.f - cur.f.f >= (ll) c[i]) {
lb = mb + 1;
if (cur.s.s > cur.f.s) {
res = c[i] + query(q,q).f.f - query(cur.s.s,cur.s.s).f.f;
}
else {
res = query(q,q).f.f - query(cur.f.s,cur.f.s).f.f;
}
}
else {
rb = mb - 1;
}
}
ans[i] = res;
*/
update(1,q,c[i]);
for (auto [val, t] : que[i][1]) {
update(t, q, -val);
}
}
return ans;
}
Compilation message
wall.cpp:1:10: fatal error: candies.h: No such file or directory
1 | #include "candies.h"
| ^~~~~~~~~~~
compilation terminated.
