#include "candies.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include "/home/hp/contests/debug.h"
#else
#define debug(...) void(37)
#endif
struct mapping {
int64_t dist = 0;
int64_t compressed = 0;
};
mapping unite(mapping l, mapping r) {
mapping res;
int64_t start = max(r.compressed, l.dist);
res.compressed = l.compressed + start - l.dist;
res.dist = r.dist + start - r.compressed;
return res;
}
struct two_sided_mapping {
mapping lower, upper;
two_sided_mapping() { }
two_sided_mapping(const int& x) {
lower = upper = mapping{};
if (x > 0) {
lower.compressed = x;
upper.dist = x;
} else {
upper.compressed = -x;
lower.dist = -x;
}
}
int64_t compressed() {
return lower.compressed + upper.compressed;
}
};
two_sided_mapping unite(two_sided_mapping l, two_sided_mapping r) {
l.lower = unite(l.lower, r.lower);
l.upper = unite(l.upper, r.upper);
return l;
}
using T = two_sided_mapping;
#define def int mid = (l + r) >> 1, rv = v + ((mid - l + 1) << 1)
struct SegTree {
vector<T> tree, tag;
int n;
SegTree(int _n) : n(_n) {
tree.resize(2 * n - 1);
tag.resize(2 * n - 1);
}
void apply(int v, T x) {
tree[v] = unite(tree[v], x);
tag[v] = unite(tag[v], x);
}
void push(int v, int l, int r) {
def;
apply(v + 1, tag[v]);
apply(rv, tag[v]);
tag[v] = T{};
}
void modify(int v, int l, int r, int ll, int rr, T x) {
if (l >= ll && rr >= r) {
apply(v, x);
return;
}
def;
push(v, l, r);
if (ll <= mid) {
modify(v + 1, l, mid, ll, rr, x);
}
if (mid < rr) {
modify(rv, mid + 1, r, ll, rr, x);
}
}
void modify(int ll, int rr, int x) {
modify(0, 0, n - 1, ll, rr, T(x));
}
T get(int p) {
int v = 0, l = 0, r = n - 1;
while (l < r) {
def;
push(v, l, r);
if (p <= mid) {
v = v + 1;
r = mid;
} else {
v = rv;
l = mid + 1;
}
}
return tree[v];
}
};
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l, std::vector<int> r, std::vector<int> v) {
int n = int(c.size());
int q = int(l.size());
vector<tuple<int, int, vector<int>>> queries;
queries.emplace_back(0, q, vector<int>{});
for (int i = 0; i < n; ++i) get<2>(queries.back()).push_back(i);
vector<int> first(n);
while (!queries.empty()) {
vector<bool> res(n);
vector<vector<int>> ask(q);
for (auto[l, r, v] : queries) {
debug(l, r, v);
if (l == r) {
for (auto i : v) {
first[i] = l;
}
} else {
int mid = (l + r) >> 1;
for (auto i : v) ask[mid].push_back(i);
}
}
SegTree st(n);
for (int i = q - 1; i >= 0; --i) {
st.modify(l[i], r[i], v[i]);
for (auto i : ask[i]) {
res[i] = st.get(i).compressed() < c[i];
}
}
vector<tuple<int, int, vector<int>>> new_queries;
for (auto[l, r, v] : queries) {
if (l == r) continue;
int mid = (l + r) >> 1;
array<vector<int>, 2> to;
for (auto i : v) {
to[res[i]].push_back(i);
}
new_queries.emplace_back(l, mid, to[1]);
new_queries.emplace_back(mid + 1, r, to[0]);
}
swap(new_queries, queries);
}
vector<vector<int>> ask(q + 1);
for (int i = 0; i < n; ++i) {
ask[first[i]].push_back(i);
}
vector<int> ans(n);
SegTree st(n);
for (int i = q - 1; i >= 0; --i) {
for (auto x : ask[i + 1]) {
auto n = st.get(x);
if (v[i] > 0) {
ans[x] = c[x] - n.upper.compressed;
} else {
ans[x] = n.lower.compressed;
}
}
st.modify(l[i], r[i], v[i]);
}
for (auto i : ask[0]) {
ans[i] = st.get(i).lower.compressed;
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
5 ms |
604 KB |
Output is correct |
| 4 |
Correct |
12 ms |
572 KB |
Output is correct |
| 5 |
Correct |
36 ms |
988 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5070 ms |
58384 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
600 KB |
Output is correct |
| 2 |
Correct |
3378 ms |
34272 KB |
Output is correct |
| 3 |
Correct |
1581 ms |
35584 KB |
Output is correct |
| 4 |
Execution timed out |
5085 ms |
48768 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
600 KB |
Output is correct |
| 2 |
Correct |
2 ms |
600 KB |
Output is correct |
| 3 |
Correct |
169 ms |
33280 KB |
Output is correct |
| 4 |
Correct |
1605 ms |
44616 KB |
Output is correct |
| 5 |
Correct |
2835 ms |
64548 KB |
Output is correct |
| 6 |
Correct |
2750 ms |
63696 KB |
Output is correct |
| 7 |
Correct |
2405 ms |
62548 KB |
Output is correct |
| 8 |
Correct |
2665 ms |
63860 KB |
Output is correct |
| 9 |
Correct |
2474 ms |
64244 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
5 ms |
604 KB |
Output is correct |
| 4 |
Correct |
12 ms |
572 KB |
Output is correct |
| 5 |
Correct |
36 ms |
988 KB |
Output is correct |
| 6 |
Execution timed out |
5070 ms |
58384 KB |
Time limit exceeded |
| 7 |
Halted |
0 ms |
0 KB |
- |
