#include "candies.h"
#include <bits/stdc++.h>
using std::array;
using std::pair;
using std::tuple;
using std::vector;
using ll = long long;
template <class T>
constexpr T infty = std::numeric_limits<T>::max() / 2;
template <class F>
struct fixed : private F {
explicit fixed(F&& f) : F(std::forward<F>(f)) {}
template <class... Args>
decltype(auto) operator()(Args&&... args) const {
return F::operator()(*this, std::forward<Args>(args)...);
}
};
template <class T> class fenwick_tree {
vector<T> data;
public:
explicit fenwick_tree(const int n) : data(n + 1) {}
void add(int i, const T& x) {
i += 1;
while (i < (int)data.size()) {
data[i] += x;
i += i & -i;
}
}
T pref(int i) const {
T ret = 0;
while (i > 0) {
ret += data[i];
i -= i & -i;
}
return ret;
}
T fold(const int l, const int r) const {
return pref(r) - pref(l);
}
};
struct func {
ll lb, ub, add;
ll eval(const ll x) {
return std::clamp(x, lb, ub) + add;
}
};
constexpr func unit = {-infty<ll>, infty<ll>, 0};
func composition(const func& f, const func& g) {
auto [l1, r1, a1] = f;
auto [l2, r2, a2] = g;
l2 -= a1;
r2 -= a1;
a2 += a1;
if (r1 <= l2) return {l2, l2, a2};
if (r2 <= l1) return {r2, r2, a2};
return {std::max(l1, l2), std::min(r1, r2), a2};
}
class segtree {
int size, logn;
vector<func> data;
void apply(const int k, const func& f) {
data[k] = composition(data[k], f);
}
void flush(const int k) {
apply(2 * k, data[k]);
apply(2 * k + 1, data[k]);
data[k] = unit;
}
void push(int k) {
const int z = __builtin_ctz(k);
for (int d = logn; d > z; --d) {
flush(k >> d);
}
}
public:
explicit segtree(const int n) {
logn = 0;
while ((1 << logn) < n) logn += 1;
size = 1 << logn;
data.resize(2 * size, unit);
}
void apply(int l, int r, const func& f) {
l += size;
r += size;
push(l);
push(r);
while (l < r) {
if (l & 1) apply(l++, f);
if (r & 1) apply(--r, f);
l >>= 1;
r >>= 1;
}
}
func get(int k) {
k += size;
for (int d = logn; d > 0; --d) {
flush(k >> d);
}
return data[k];
}
};
vector<int> distribute_candies(vector<int> C, vector<int> L, vector<int> R, vector<int> V) {
const int N = (int)C.size();
const int Q = (int)L.size();
for (auto& x : R) x += 1;
if (N <= 2000 and Q <= 2000) {
vector<int> X(N);
for (int q = 0; q < Q; ++q) {
for (int i = L[q]; i < R[q]; ++i) {
X[i] = std::clamp(X[i] + V[q], 0, C[i]);
}
}
return X;
}
if (*std::min_element(V.begin(), V.end()) > 0) {
fenwick_tree<ll> fen(N);
for (int q = 0; q < Q; ++q) {
fen.add(L[q], V[q]);
fen.add(R[q], -V[q]);
}
vector<int> X(N);
for (int i = 0; i < N; ++i) {
const ll tmp = fen.pref(i + 1);
X[i] = tmp >= C[i] ? C[i] : tmp;
}
return X;
}
if (std::count(C.begin(), C.end(), C[0]) == N) {
segtree seg(N);
for (int q = 0; q < Q; ++q) {
seg.apply(L[q], R[q], composition({-infty<int>, infty<int>, V[q]}, {0, C[0], 0}));
}
vector<int> X(N);
for (int i = 0; i < N; ++i) {
X[i] = seg.get(i).eval(0);
}
return X;
}
vector<pair<int, int>> sorted(N);
for (int i = 0; i < N; ++i) {
sorted[i] = {C[i], i};
}
std::sort(sorted.begin(), sorted.end());
vector<ll> sum(Q + 1);
std::map<int, pair<int, int>> last;
const auto calc = [&](const int i, const int t) {
const auto [s, x] = last.upper_bound(i)->second;
return (x == 0 ? 0 : sorted[i].first) + (sum[t] - sum[s]);
};
last[0] = {N, 0};
for (int q = 0; q < Q; ++q) {
sum[q + 1] = sum[q] + V[q];
int ng = -1, ok = N;
while (std::abs(ng - ok) > 1) {
const int md = (ok + ng) / 2;
const int val = calc(md, q + 1);
if (val < 0 or sorted[md].first < val) {
ng = md;
} else {
ok = md;
}
}
while (last.begin() -> first < ok) {
last.erase(last.begin());
}
last[ok] = {q + 1, V[q] > 0};
}
vector<int> X(N);
for (int i = 0; i < N; ++i) {
X[sorted[i].second] = calc(i, Q);
}
return X;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
5 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
118 ms |
8816 KB |
Output is correct |
| 2 |
Correct |
122 ms |
8808 KB |
Output is correct |
| 3 |
Correct |
112 ms |
8884 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
166 ms |
5112 KB |
Output is correct |
| 3 |
Correct |
133 ms |
17200 KB |
Output is correct |
| 4 |
Correct |
462 ms |
25680 KB |
Output is correct |
| 5 |
Correct |
447 ms |
26108 KB |
Output is correct |
| 6 |
Correct |
417 ms |
26384 KB |
Output is correct |
| 7 |
Correct |
461 ms |
25700 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Execution timed out |
5023 ms |
6488 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
5 ms |
340 KB |
Output is correct |
| 6 |
Correct |
118 ms |
8816 KB |
Output is correct |
| 7 |
Correct |
122 ms |
8808 KB |
Output is correct |
| 8 |
Correct |
112 ms |
8884 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
166 ms |
5112 KB |
Output is correct |
| 11 |
Correct |
133 ms |
17200 KB |
Output is correct |
| 12 |
Correct |
462 ms |
25680 KB |
Output is correct |
| 13 |
Correct |
447 ms |
26108 KB |
Output is correct |
| 14 |
Correct |
417 ms |
26384 KB |
Output is correct |
| 15 |
Correct |
461 ms |
25700 KB |
Output is correct |
| 16 |
Correct |
0 ms |
212 KB |
Output is correct |
| 17 |
Correct |
1 ms |
212 KB |
Output is correct |
| 18 |
Execution timed out |
5023 ms |
6488 KB |
Time limit exceeded |
| 19 |
Halted |
0 ms |
0 KB |
- |
