#include "candies.h"
#include <vector>
#include "bits/stdc++.h"
using namespace std;
#define int long long
struct segtree_basic {
struct node {
int lazy;
int lc, rc;
int mx, mn;
int sum;
int type; // 1: ADD, 2: SET
};
vector<node> st;
int stok;
void init(int l, int r, int idx) {
st[idx].lazy = 0;
st[idx].sum = 0;
st[idx].mx = st[idx].mn = 0;
st[idx].type = 1;
st[idx].lc = l, st[idx].rc = r;
if(l == r) return;
init(l, (l + r) >> 1, (idx << 1) + 1);
init(((l + r) >> 1) + 1, r, (idx << 1) + 2);
}
void push_down(int idx) {
if(st[idx].type == 1 && st[idx].lazy == 0) {
// no update
return;
}
if(st[idx].type == 1) {
st[(idx << 1) + 1].lazy += st[idx].lazy;
st[(idx << 1) + 1].mx += st[idx].lazy;
st[(idx << 1) + 1].mn += st[idx].lazy;
st[(idx << 1) + 1].sum += st[idx].lazy * (st[(idx << 1) + 1].rc - st[(idx << 1) + 1].lc + 1);
st[(idx << 1) + 2].lazy += st[idx].lazy;
st[(idx << 1) + 2].mx += st[idx].lazy;
st[(idx << 1) + 2].mn += st[idx].lazy;
st[(idx << 1) + 2].sum += st[idx].lazy * (st[(idx << 1) + 2].rc - st[(idx << 1) + 2].lc + 1);
}
else {
st[(idx << 1) + 1].lazy = st[idx].lazy;
st[(idx << 1) + 1].mx = st[idx].lazy;
st[(idx << 1) + 1].mn = st[idx].lazy;
st[(idx << 1) + 1].sum = st[idx].lazy * (st[(idx << 1) + 1].rc - st[(idx << 1) + 1].lc + 1);
st[(idx << 1) + 1].type = 2;
st[(idx << 1) + 2].lazy = st[idx].lazy;
st[(idx << 1) + 2].mx = st[idx].lazy;
st[(idx << 1) + 2].mn = st[idx].lazy;
st[(idx << 1) + 2].sum = st[idx].lazy * (st[(idx << 1) + 2].rc - st[(idx << 1) + 2].lc + 1);
st[(idx << 1) + 2].type = 2;
}
st[idx].type = 1;
st[idx].lazy = 0;
}
void push_up(int idx) {
st[idx].mn = min(st[(idx << 1) + 1].mn, st[(idx << 1) + 2].mn);
st[idx].mx = max(st[(idx << 1) + 1].mx, st[(idx << 1) + 2].mx);
st[idx].sum = st[(idx << 1) + 1].sum + st[(idx << 1) + 2].sum;
}
void u1(int l, int r, int constl, int constr, int idx, int val) {
if(l <= constl && constr <= r) {
st[idx].lazy += val;
st[idx].mn += val, st[idx].mx += val;
st[idx].sum += val * (st[idx].rc - st[idx].lc + 1);
return;
}
int mid = (constl + constr) >> 1;
push_down(idx);
if(mid < l || r < constl) u1(l, r, mid+1, constr, (idx << 1) + 2, val);
else if(constr < l || r < mid+1) u1(l, r, constl, mid, (idx << 1) + 1, val);
else {
u1(l, r, constl, mid, (idx << 1) + 1, val);
u1(l, r, mid + 1, constr, (idx << 1) + 2, val);
}
push_up(idx);
}
void u2(int l, int r, int constl, int constr, int idx, int val) {
if(l <= constl && constr <= r) {
st[idx].type = 2;
st[idx].lazy = val;
st[idx].mn = val, st[idx].mx = val;
st[idx].sum = val * (st[idx].rc - st[idx].lc + 1);
return;
}
int mid = (constl + constr) >> 1;
push_down(idx);
if(mid < l || r < constl) u2(l, r, mid+1, constr, (idx << 1) + 2, val);
else if(constr < l || r < mid+1) u2(l, r, constl, mid, (idx << 1) + 1, val);
else {
u2(l, r, constl, mid, (idx << 1) + 1, val);
u2(l, r, mid + 1, constr, (idx << 1) + 2, val);
}
push_up(idx);
}
int qu1(int l, int r, int constl, int constr, int idx) {
if(l <= constl && constr <= r) return st[idx].mn;
int mid = (constl + constr) >> 1;
push_down(idx);
if(mid < l || r < constl) return qu1(l, r, mid+1, constr, (idx << 1) + 2);
else if(constr < l || r< mid+1) return qu1(l, r, constl, mid, (idx << 1) + 1);
else {
return min(
qu1(l, r, constl, mid, (idx << 1) + 1),
qu1(l, r, mid+1, constr, (idx << 1) + 2)
);
}
}
int qu2(int l, int r, int constl, int constr, int idx) {
if(l <= constl && constr <= r) return st[idx].mx;
int mid = (constl + constr) >> 1;
push_down(idx);
if(mid < l || r < constl) return qu2(l, r, mid+1, constr, (idx << 1) + 2);
else if(constr < l || r< mid+1) return qu2(l, r, constl, mid, (idx << 1) + 1);
else {
return max(
qu2(l, r, constl, mid, (idx << 1) + 1),
qu2(l, r, mid+1, constr, (idx << 1) + 2)
);
}
}
int qu3(int l, int r, int constl, int constr, int idx) {
if(l <= constl && constr <= r) return st[idx].sum;
int mid = (constl + constr) >> 1;
push_down(idx);
if(mid < l || r < constl) return qu3(l, r, mid+1, constr, (idx << 1) + 2);
else if(constr < l || r< mid+1) return qu3(l, r, constl, mid, (idx << 1) + 1);
else {
return qu3(l, r, constl, mid, (idx << 1) + 1) + qu3(l, r, mid+1, constr, (idx << 1) + 2);
}
}
int qu4(int l, int r, int constl, int constr, int idx, int val) {
if(l <= constl && constr <= r) {
if(st[idx].mx < val) return -1;
while(constl < constr) {
int mid = (constl + constr) >> 1;
push_down(idx);
if(st[(idx << 1) + 1].mx >= val) idx = (idx << 1) + 1, constr = mid;
else idx = (idx << 1) + 2, constl = mid + 1;
}
return constl;
}
int mid = (constl + constr) >> 1;
push_down(idx);
if(mid < l || r < constl) return qu4(l, r, mid+1, constr, (idx << 1) + 2, val);
else if(constr < l || r< mid+1) return qu4(l, r, constl, mid, (idx << 1) + 1, val);
else {
int lc = qu4(l, r, constl, mid, (idx << 1) + 1, val);
if(lc != -1) return lc;
return qu4(l, r, mid+1, constr, (idx << 1) + 2, val);
}
}
int qu5(int l, int r, int constl, int constr, int idx, int val) {
if(l <= constl && constr <= r) {
if(st[idx].mn > val) return -1;
while(constl < constr) {
int mid = (constl + constr) >> 1;
push_down(idx);
if(st[(idx << 1) + 1].mn <= val) idx = (idx << 1) + 1, constr = mid;
else idx = (idx << 1) + 2, constl = mid + 1;
}
return constl;
}
int mid = (constl + constr) >> 1;
push_down(idx);
if(mid < l || r < constl) return qu5(l, r, mid+1, constr, (idx << 1) + 2, val);
else if(constr < l || r< mid+1) return qu5(l, r, constl, mid, (idx << 1) + 1, val);
else {
int lc = qu5(l, r, constl, mid, (idx << 1) + 1, val);
if(lc != -1) return lc;
return qu5(l, r, mid+1, constr, (idx << 1) + 2, val);
}
}
int qu6(int l, int r, int constl, int constr, int idx, int val) {
if(l <= constl && constr <= r) {
if(st[idx].mx < val) return -1;
while(constl < constr) {
int mid = (constl + constr) >> 1;
push_down(idx);
if(st[(idx << 1) + 2].mx >= val) idx = (idx << 1) + 2, constl = mid + 1;
else idx = (idx << 1) + 1, constr = mid;
}
return constl;
}
int mid = (constl + constr) >> 1;
push_down(idx);
if(mid < l || r < constl) return qu6(l, r, mid+1, constr, (idx << 1) + 2, val);
else if(constr < l || r< mid+1) return qu6(l, r, constl, mid, (idx << 1) + 1, val);
else {
int rc = qu6(l, r, mid+1, constr, (idx << 1) + 2, val);
if(rc != -1) return rc;
return qu6(l, r, constl, mid, (idx << 1) + 1, val);
}
}
int qu7(int l, int r, int constl, int constr, int idx, int val) {
if(l <= constl && constr <= r) {
if(st[idx].mn > val) return -1;
while(constl < constr) {
int mid = (constl + constr) >> 1;
push_down(idx);
if(st[(idx << 1) + 2].mn <= val) idx = (idx << 1) + 2, constl = mid + 1;
else idx = (idx << 1) + 1, constr = mid;
}
return constl;
}
int mid = (constl + constr) >> 1;
push_down(idx);
if(mid < l || r < constl) return qu7(l, r, mid+1, constr, (idx << 1) + 2, val);
else if(constr < l || r< mid+1) return qu7(l, r, constl, mid, (idx << 1) + 1, val);
else {
int rc = qu7(l, r, mid+1, constr, (idx << 1) + 2, val);
if(rc != -1) return rc;
return qu7(l, r, constl, mid, (idx << 1) + 1, val);
}
}
void resize(int k) {
stok = k + 5;
st.resize(4 * stok);
init(0, stok, 0);
}
void range_add(int l, int r, int v) { u1(l, r, 0, stok, 0, v); }
void range_assign(int l, int r, int v) { u2(l, r, 0, stok, 0, v); }
int query_min(int l, int r) { return qu1(l, r, 0, stok, 0); }
int query_max(int l, int r) { return qu2(l ,r, 0, stok, 0); }
int query_sum(int l, int r) { return qu3(l, r, 0, stok, 0); }
int query_firstAtLeast(int l, int r, int v) { return qu4(l, r, 0, stok, 0, v); }
int query_firstAtMost(int l, int r, int v) { return qu5(l, r, 0, stok, 0, v); }
int query_lastAtLeast(int l, int r, int v) { return qu6(l, r, 0, stok, 0, v); }
int query_lastAtMost(int l, int r, int v) { return qu7(l, r, 0, stok, 0, v); }
};
#undef int
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
std::vector<int> r, std::vector<int> v) {
int n = c.size();
std::vector<int> s(n, 0);
#define int long long
vector<int> ins[n+1], del[n+1];
int m = l.size();
segtree_basic stb;
stb.resize(m);
for(int i=0; i<m; i++) {
ins[l[i]].push_back(i);
del[r[i] + 1].push_back(i);
}
for(int i=0; i<n; i++) {
for(int x: del[i]) {
stb.range_add(x + 1, m, -v[x]);
}
for(int x: ins[i]) {
stb.range_add(x + 1, m, v[x]);
}
int res = stb.query_sum(m, m);
int lb = 0, rb = m;
while(lb < rb) {
int mid = (lb + rb + 1) >> 1;
int mx = stb.query_max(mid, m);
int mn = stb.query_min(mid, m);
if(mx - mn > c[i]) lb = mid;
else rb = mid - 1;
}
int mx = stb.query_max(lb, m);
int mn = stb.query_min(lb, m);
int dist = mx - mn;
if(dist <= c[i]) {
s[i] = res;
}
else {
int buh = stb.query_max(lb, lb);
if(buh > res) {
buh -= dist;
s[i] = res - buh;
}
else {
buh += dist;
s[i] = res - (mx - c[i]);
}
}
}
return s;
}
/*
g++ -std=c++17 -O2 -o candies buh.cpp candies.cpp
./candies < input.txt
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1674 ms |
73500 KB |
Output is correct |
| 2 |
Correct |
1811 ms |
72724 KB |
Output is correct |
| 3 |
Correct |
1876 ms |
72564 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 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 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
151 ms |
54888 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
