#include "candies.h"
#include <algorithm>
#include <bitset>
#include <cstdint>
#include <cstring>
#include <iostream>
#include <limits.h>
#include <math.h>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define ll long long
#define loop(X, N) for(int X = 0; X < (N); X++)
#define all(V) V.begin(), V.end()
#define rall(V) V.rbegin(), V.rend()
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
typedef tuple<ll, pair<ll, int>, pair<ll, int>> Entry;
struct SegTree {
int n = -1, N = -1;
vector<Entry> tree; //sum, min, max
vi lazy;
Entry id = { 0, {LLONG_MAX / 2, 0}, {LLONG_MIN / 2, 0}};
SegTree(int _n) {
n = _n;
N = 1;
while (N < n) N *= 2;
tree.resize(2 * N);
loop(i, n) {
tree[N + i] = { 0, { 0, i}, { 0, i }};
}
for (int i = N - 1; i >= 1; i--) {
tree[i] = merge(tree[2 * i], tree[2 * i + 1]);
}
lazy.resize(2 * N, 0);
//sums = SumTree(n);
}
Entry merge(Entry a, Entry b) {
auto [s1, min1, max1] = a;
auto [s2, min2, max2] = b;
int s = s1 + s2;
ii mn;
if (min1.first < min2.first) {
mn.first = min1.first;
mn.second = min1.second;
}
else {
mn.first = min2.first;
mn.second = min2.second;
}
ii mx;
if (max1.first > max2.first) {
mx.first = max1.first;
mx.second = max1.second;
}
else {
mx.first = max2.first;
mx.second = max2.second;
}
return {s, mn, mx};
}
void add2(int idx, ll v, int i = 1, int tl = 0, int tr = -1) {
if (tr == -1)
tr = N;
if (tr - tl == 1) {
get<0>(tree[i]) += v;
return;
}
int tm = (tl + tr) / 2;
if (idx < tm) {
add2(idx, v, 2 * i, tl, tm);
}
else {
add2(idx, v, 2 * i + 1, tm, tr);
}
tree[i] = merge(tree[2 * i], tree[2 * i + 1]);
}
void add(int l, int r, ll v, int i = 1, int tl = 0, int tr = -1) {
if (tr == -1)
tr = N;
if (lazy[i]) {
get<1>(tree[i]).first += lazy[i];
get<2>(tree[i]).first += lazy[i];
if (tr - tl > 1) {
lazy[2 * i] += lazy[i];
lazy[2 * i + 1] += lazy[i];
}
lazy[i] = 0;
}
if (l >= tr || r <= tl) {
return;
}
if (tl >= l && tr <= r) {
get<1>(tree[i]).first += v;
get<2>(tree[i]).first += v;
if (tr - tl > 1) {
lazy[2 * i] += v;
lazy[2 * i + 1] += v;
}
return;
}
int tm = (tl + tr) / 2;
if (l < tm) {
add(l, r, v, 2 * i, tl, tm);
add(l, r, v, 2 * i + 1, tm, tr);
}
else {
add(l, r, 0, 2 * i, tl, tm);
add(l, r, v, 2 * i + 1, tm, tr);
}
tree[i] = merge(tree[2 * i], tree[2 * i + 1]);
}
void set(int idx, const Entry& v, int i = 1, int tl = 0, int tr = -1) {
if (tr == -1)
tr = N;
if (tr - tl == 1) {
tree[i] = v;
return;
}
int tm = (tl + tr) / 2;
if (idx < tm) {
set(idx, v, 2 * i, tl, tm);
}
else {
set(idx, v, 2 * i + 1, tm, tr);
}
tree[i] = merge(tree[2 * i], tree[2 * i + 1]);
}
Entry getRange(int l, int r, int i = 1, int tl = 0, int tr = -1) {
if (tr == -1)
tr = N;
if (lazy[i]) {
get<1>(tree[i]).first += lazy[i];
get<2>(tree[i]).first += lazy[i];
if (tr - tl > 1) {
lazy[2 * i] += lazy[i];
lazy[2 * i + 1] += lazy[i];
}
lazy[i] = 0;
}
if (l >= tr || r <= tl)
return id;
if (tl >= l && tr <= r)
return tree[i];
int tm = (tl + tr) / 2;
return merge(getRange(l, r, 2 * i, tl, tm), getRange(l, r, 2 * i + 1, tm, tr));
}
};
vi distribute_candies(vi c, vi ls, vi rs, vi vs) {
int n = c.size();
int q = ls.size();
SegTree segTree(q + 1);
vvii queryStarts(n), queryEnds(n);
loop(i, q) {
int l = ls[i];
int r = rs[i];
int v = vs[i];
queryStarts[l].push_back({v, i + 1});
queryEnds[r].push_back({v, i + 1});
}
vi s(n);
loop(i, n) {
for (auto [v, idx] : queryStarts[i]) {
segTree.add2(idx, v);
segTree.add(idx, q + 1, v);
}
segTree.set(0, {0, {0, 0}, {c[i], 0}});
int l = 0, r = q;
while (l < r) {
int m = (l + r + 1) / 2;
//ll diff = sufMax[m].first - sufMin[m].first;
auto [sum, mn, mx] = segTree.getRange(m, q + 1);
ll diff = mx.first - mn.first;
if (diff < c[i]) {
r = m - 1;
}
else {
l = m;
}
}
auto [sum, mn, mx] = segTree.getRange(l, q + 1);
if (l == 0 && mx.first - mn.first <= c[i]) {
//s[i] = cumul.back();
int extra = get<0>(segTree.getRange(0, q + 1));
s[i] = extra;
}
else {
//int lastMin = sufMin[l].second;
//int lastMax = sufMax[l].second;
int lastMin = mn.second;
int lastMax = mx.second;
if (lastMin >= lastMax) {
l = lastMin;
s[i] = 0;
}
else {
l = lastMax;
s[i] = c[i];
}
//s[i] += cumul.back() - cumul[l];
ll extra = get<0>(segTree.getRange(l + 1, q + 1));
s[i] += extra;
}
for (auto [v, idx] : queryEnds[i]) {
segTree.add2(idx, -v);
segTree.add(idx, q + 1, -v);
}
}
return s;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1909 ms |
52240 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
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 |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
258 ms |
33724 KB |
Output is correct |
| 4 |
Correct |
559 ms |
13660 KB |
Output is correct |
| 5 |
Correct |
1663 ms |
45980 KB |
Output is correct |
| 6 |
Correct |
1772 ms |
46772 KB |
Output is correct |
| 7 |
Correct |
1501 ms |
47372 KB |
Output is correct |
| 8 |
Correct |
1672 ms |
46012 KB |
Output is correct |
| 9 |
Correct |
1838 ms |
47540 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
