| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1203846 | badge881 | Distributing Candies (IOI21_candies) | C++20 | 0 ms | 0 KiB |
#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
const int MxN = 2e5 + 5;
int n, q;
long long lz[MxN * 4];
const long long Inf = 1e18;
// every segmentis [a;b]
struct node
{
long long val;
pair<long long, long long> mx, mn;
node() : val(0), mx({0, -1}), mn({0, -1}) {}
node(long long val, long long idx) : val(val), mx({val, idx}), mn({val, idx}) {}
node(long long mx, long long mn, long long idx) : val(0), mx({mx, idx}), mn({mn, idx}) {}
friend node operator+(const node &l, const node &r)
{
node res = node();
res.val = l.val + r.val;
res.mx = max(l.mx, r.mx);
res.mn = min(l.mn, r.mn);
return res;
}
} segm[MxN * 4];
pair<node, long long> operator+(pair<node, long long> c, node o)
{
c.first = c.first + o;
return c;
}
void push(long long l, long long r, long long idx)
{
segm[idx].val += lz[idx];
segm[idx].mx.first += lz[idx];
segm[idx].mn.first += lz[idx];
if (l < r)
{
lz[idx * 2 + 1] += lz[idx];
lz[idx * 2 + 2] += lz[idx];
}
lz[idx] = 0;
}
void build(long long l, long long r, long long idx)
{
if (l == r)
return void(segm[idx] = node(0, l));
long long mid = (l + r) >> 1long long;
build(l, mid, idx * 2 + 1);
build(mid + 1, r, idx * 2 + 2);
segm[idx] = segm[idx * 2 + 1] + segm[idx * 2 + 2];
}
void update(long long l, long long r, long long idx, long long tl, long long tr, long long val)
{
push(l, r, idx);
if (l > tr || r < tl)
return;
if (l >= tl && r <= tr)
{
lz[idx] += val;
push(l, r, idx);
return;
}
long long mid = (l + r) >> 1long long;
push(l, mid, idx * 2 + 1);
push(mid + 1, r, idx * 2 + 2);
update(l, mid, idx * 2 + 1, tl, tr, val);
update(mid + 1, r, idx * 2 + 2, tl, tr, val);
segm[idx] = segm[idx * 2 + 1] + segm[idx * 2 + 2];
}
pair<node, long long> query(long long l, long long r, long long idx, long long k, node cur)
{
push(l, r, idx);
if (l == r)
return {segm[idx] + cur, l};
long long mid = (l + r) >> 1long long;
push(l, mid, idx * 2 + 1);
push(mid + 1, r, idx * 2 + 2);
node qrr = segm[idx * 2 + 2] + cur;
if (qrr.mx.first - qrr.mn.first > k)
return query(mid + 1, r, idx * 2 + 2, k, cur);
else
return query(l, mid, idx * 2 + 1, k, qrr);
}
node oo(long long l, long long r, long long idx, long long pos)
{
push(l, r, idx);
if (l == r)
return segm[idx];
long long mid = (l + r) >> 1LL;
push(l, mid, idx * 2 + 1);
push(mid + 1, r, idx * 2 + 2);
if (pos <= mid)
return oo(l, mid, idx * 2 + 1, pos);
else
return oo(mid + 1, r, idx * 2 + 2, pos);
}
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v)
{
n = c.size();
q = l.size();
vector<int> s(n);
vector<vector<pair<long long, long long>>> cq(n, vector<pair<long long, long long>>());
for (int i = 0; i < q; i++)
{
cq[l[i]].emplace_back(v[i], i);
if (r[i] + 1 < n)
cq[r[i] + 1].emplace_back(-v[i], i);
}
build(0, q - 1 + 2, 0);
long long cur = 0;
update(0, q - 1 + 2, 0, 0, q - 1 + 2, Inf);
update(0, q - 1 + 2, 0, 1, q - 1 + 2, -Inf);
for (int i = 0; i < n; i++)
{
for (auto &[x, y] : cq[i])
update(0, q - 1 + 2, 0, y + 2, q - 1 + 2, x), cur += x;
auto cqr = query(0, q - 1 + 2, 0, c[i], node(-Inf, Inf, 0));
auto z = cqr.first;
if (z.mx.second < z.mn.second)
s[i] = cur - z.mn.first;
else
s[i] = cur - (z.mx.first - c[i]);
}
return s;
}