| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 806065 | ono_de206 | Distributing Candies (IOI21_candies) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "candies.h"
#include<bits/stdc++.h>
using namespace std;
#define in insert
#define all(x) x.begin(),x.end()
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second
// #define int long long
typedef long long ll;
typedef vector<int> vi;
typedef set<int> si;
typedef multiset<int> msi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
const int mxn = 2e5 + 10;
const long long inf = 1e18 + 10;
struct segTreeBeats {
int l, r, m;
long long sum, max1, max2, min1, min2, maxc, minc, lz;
segTreeBeats *le, *ri;
void up() {
assert(le != NULL);
assert(ri != NULL);
sum = le->sum + ri->sum;
max1 = max(le->max1, ri->max1);
min1 = min(le->min1, ri->min1);
max2 = -inf;
min2 = inf;
if(le->max1 == ri->max1) {
maxc = le->maxc + ri->maxc;
max2 = max(le->max2, ri->max2);
} else {
if(le->max1 > ri->max1) {
maxc = le->maxc;
max2 = max(le->max2, ri->max1);
} else {
maxc = ri->maxc;
max2 = max(le->max1, ri->max2);
}
}
if(le->min1 == ri->min1) {
minc = le->minc + ri->minc;
min2 = min(le->min2, ri->min2);
} else {
if(le->min1 < ri->min1) {
minc = le->minc;
min2 = min(le->min2, ri->min1);
} else {
minc = ri->minc;
min2 = min(le->min1, ri->min2);
}
}
}
segTreeBeats(int _l, int _r, vector<int> &a) {
l = _l; r = _r; m = (l + r) / 2;
lz = 0;
if(l == r) {
sum = max1 = min1 = a[l];
maxc = minc = 1;
max2 = -inf; min2 = inf;
le = ri = NULL;
return;
}
le = new segTreeBeats(l, m, a);
ri = new segTreeBeats(m + 1, r, a);
up();
}
void proAdd(long long x) {
sum += x * (r - l + 1);
max1 += x; min1 += x;
if(max2 != -inf) max2 += x;
if(min2 != inf) min2 += x;
lz += x;
}
void proMax(long long x) {
if(x >= max1) return;
sum -= maxc * max1;
max1 = x;
sum += maxc * max1;
if(l == r) {
min1 = x;
} else {
if(x <= min1) min1 = x;
else if(x < min2) min2 = x;
}
}
void proMin(long long x) {
if(x <= min1) return;
sum -= minc * min1;
min1 = x;
sum += minc * min1;
if(l == r) {
max1 = x;
} else {
if(x >= max1) max1 = x;
else if(x > max2) max2 = x;
}
}
void pro() {
if(l == r) return;
// if(le == NULL) le = new segTreeBeat(l, m);
// if(ri == NULL) ri = new segTreeBeat(m + 1, r);
le->proAdd(lz);
ri->proAdd(lz);
lz = 0;
le->proMax(max1);
ri->proMax(max1);
le->proMin(min1);
ri->proMin(min1);
}
void add(int x, int y, long long v) {
if(l > y || r < x) return;
if(l >= x && r <= y) {
proAdd(v);
return;
}
pro();
le->add(x, y, v);
ri->add(x, y, v);
up();
}
void mnn(int x, int y, long long v) {
if(l > y || r < x || max1 <= v) return;
if(l >= x && r <= y && max2 < v) {
proMax(v);
return;
}
pro();
le->mnn(x, y, v);
ri->mnn(x, y, v);
up();
}
void mxx(int x, int y, long long v) {
if(l > y || r < x || min1 >= v) return;
if(l >= x && r <= y && min2 > v) {
proMin(v);
return;
}
pro();
le->mxx(x, y, v);
ri->mxx(x, y, v);
up();
}
long long getSum(int x, int y) {
if(l > y || r < x) return 0LL;
if(l >= x && r <= y) return sum;
pro();
return le->getSum(x, y) + ri->getSum(x, y);
}
long long getMax(int x, int y) {
if(l > y || r < x) return -inf;
if(l >= x && r <= y) return max1;
pro();
return max(le->getMax(x, y), ri->getMax(x, y));
}
long long getMin(int x, int y) {
if(l > y || r < x) return inf;
if(l >= x && r <= y) return min1;
pro();
return max(le->getMin(x, y), ri->getMin(x, y));
}
~segTreeBeats() {
if(le != NULL) delete le;
if(ri != NULL) delete ri;
}
};
const int mxn = 2e5 + 10;
int a[mxn];
struct seg {
int mx, mn, resmx, resmn, lz, zero, ismax;
} d[mxn * 4];
void up(int i) {
d[i].mx = d[i * 2 + 1].mx;
d[i].resmx = d[i * 2 + 1].resmx;
d[i].mn = d[i * 2].mn;
d[i].resmn = d[i * 2].resmn;
}
void pro(int i, int l, int r) {
if(d[i].zero) {
d[i].mx = d[i].mn = 0;
d[i].resmx = a[r];
d[i].resmn = a[l];
d[i].lz = d[i].ismax = 0;
if(l < r) {
d[i * 2].zero = 1;
d[i * 2 + 1].zero = 1;
d[i * 2].ismax = d[i * 2].lz = 0;
d[i * 2 + 1].ismax = d[i * 2 + 1].lz = 0;
}
}
if(d[i].ismax) {
d[i].mx = a[r];
d[i].mn = a[l];
d[i].resmx = d[i].resmn = 0;
d[i].lz = d[i].zero = 0;
if(l < r) {
d[i * 2].ismax = 1;
d[i * 2 + 1].ismax = 1;
d[i * 2].zero = d[i * 2].lz = 0;
d[i * 2 + 1].zero = d[i * 2 + 1].lz = 0;
}
}
if(d[i].lz != 0) {
d[i].mx += d[i].lz;
d[i].mn += d[i].lz;
d[i].resmx -= d[i].lz;
d[i].resmn -= d[i].lz;
if(l < r) {
d[i * 2].lz += d[i].lz;
d[i * 2 + 1].lz += d[i].lz;
}
}
d[i].lz = d[i].zero = d[i].ismax = 0;
}
void build(int l, int r, int i) {
d[i].lz = d[i].zero = d[i].ismax = 0;
if(l == r) {
d[i].mx = d[i].mn = 0;
d[i].resmx = d[i].resmn = a[l];
return;
}
int m = (l + r) / 2;
build(l, m, i * 2);
build(m + 1, r, i * 2 + 1);
up(i);
}
void setZero(int l, int r, int i, int x, int y) {
pro(i, l, r);
if(x > y) return;
if(l > y || r < x) return;
if(l >= x && r <= y) {
d[i].zero = 1;
pro(i, l, r);
return;
}
int m = (l + r) / 2;
setZero(l, m, i * 2, x, y);
setZero(m + 1, r, i * 2 + 1, x, y);
up(i);
}
void setMax(int l, int r, int i, int x, int y) {
pro(i, l, r);
if(x > y) return;
if(l > y || r < x) return;
if(l >= x && r <= y) {
d[i].ismax = 1;
pro(i, l, r);
return;
}
int m = (l + r) / 2;
setMax(l, m, i * 2, x, y);
setMax(m + 1, r, i * 2 + 1, x, y);
up(i);
}
void add(int l, int r, int i, int x, int y, int val) {
pro(i, l, r);
if(x > y) return;
if(l > y || r < x) return;
if(l >= x && r <= y) {
d[i].lz += val;
pro(i, l, r);
return;
}
int m = (l + r) / 2;
add(l, m, i * 2, x, y, val);
add(m + 1, r, i * 2 + 1, x, y, val);
up(i);
}
int getLeftMax(int l, int r, int i, int val) {
if(d[i].mx < val) return -1;
if(l == r) return l;
int m = (l + r) / 2;
int ret = getLeftMax(l, m, i * 2, val);
if(ret == -1) ret = getLeftMax(m + 1, r, i * 2 + 1, val);
return ret;
}
int getLeftResmax(int l, int r, int i, int val) {
if(d[i].resmx < val) return -1;
if(l == r) return l;
int m = (l + r) / 2;
int ret = getLeftResax(l, m, i * 2, val);
if(ret == -1) ret = getLeftResmax(m + 1, r, i * 2 + 1, val);
return ret;
}
vi distribute_candies(vi c, vi l, vi r, vi v) {
int n = c.size(), q = l.size();
vector<long long> ret(n);
if(n * q <= 2000 * 2000) {
for(int i = 0; i < q; i++) {
for(int j = l[i]; j <= r[i]; j++) {
ret[j] += v[i];
ret[j] = min(1ll * c[j], max(0ll, ret[j]));
}
}
return vector<int>(all(ret));
}
if(*min_element(all(v)) >= 0) {
for(int i = 0; i < q; i++) {
ret[l[i]] += v[i];
if(r[i] + 1 < n) ret[r[i] + 1] -= v[i];
}
for(int i = 1; i < n; i++) {
ret[i] += ret[i - 1];
}
for(int i = 0; i < n; i++) {
ret[i] = min(1ll * c[i], max(0ll, ret[i]));
}
return vector<int>(all(ret));
}
if(*max_element(all(c)) == *min_element(all(c))) {
vector<int> tmp(n, 0);
segTreeBeats *st = new segTreeBeats(0, n - 1, tmp);
for(int i = 0; i < q; i++) {
st->add(l[i], r[i], v[i]);
st->mnn(l[i], r[i], c[0]);
st->mxx(l[i], r[i], 0);
}
for(int i = 0; i < n; i++) {
ret[i] = st->getSum(i, i);
}
return vector<int>(all(ret));
}
sort(all(c));
for(int i = 1; i <= n; i++) {
a[i] = c[i - 1];
}
build(1, n, 1);
for(int j = 0; j < q; j++) {
l[j]++; r[j]++;
if(v[i] == 0) continue;
if(v[i] < 0) {
int p = getLeftMax(1, n, 1, -v[i]);
if(p == -1) p = n + 1;
setZero(1, n, 1, 1, p - 1);
add(1, n, 1, p, n, v[i]);
} else {
int p = getLeftResmax(1, n, 1, v[i]);
if(p == -1) p = n + 1;
setMax(1, n, 1, 1, p - 1);
add(1, n, 1, p, n, v[i]);
}
}
for(int i = 0; i < n; i++) {
ret[i] = get(1, n, 1, i + 1);
}
return vector<int>(all(ret));
}