#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;
struct info {
ll sum, min, max;
};
constexpr info unit = {0, 0, 0};
info merge(const info& l, const info& r) {
return {l.sum + r.sum, std::min(l.min, l.sum + r.min), std::max(l.max, l.sum + r.max)};
}
struct segtree {
int size, logn;
vector<info> data;
explicit segtree(const int n) {
logn = 0;
while ((1 << logn) < n) logn += 1;
size = 1 << logn;
data.resize(2 * size, unit);
}
void set(int i, const info& o) {
i += size;
data[i] = o;
while (i > 1) {
i >>= 1;
data[i] = merge(data[2 * i], data[2 * i + 1]);
}
}
info prod(int l, int r) const {
l += size;
r += size;
info sl = unit, sr = unit;
while (l < r) {
if (l & 1) sl = merge(sl, data[l++]);
if (r & 1) sr = merge(data[--r], sr);
l >>= 1;
r >>= 1;
}
return merge(sl, sr);
}
info prod() const {
return data[1];
}
template <class F>
int min_left(const F& f) const {
if (f(data[1])) {
return 0;
}
info acc = unit;
int k = 1;
while (k < size) {
const int r = 2 * k + 1;
if (f(merge(data[r], acc))) {
acc = merge(data[r], acc);
k <<= 1;
} else {
k = r;
}
}
return k - size + 1;
}
};
vector<int> distribute_candies(vector<int> C, vector<int> L, vector<int> R, vector<int> V) {
const int N = C.size();
const int Q = L.size();
vector<vector<int>> enable(N), disable(N);
for (int i = 0; i < Q; ++i) {
enable[L[i]].push_back(i);
disable[R[i]].push_back(i);
}
segtree seg(Q);
vector<int> res(N);
for (int i = 0; i < N; ++i) {
for (const int q : enable[i]) {
seg.set(q, {V[q], std::min(0, V[q]), std::max(0, V[q])});
}
const int l = seg.min_left([&](const info& x) {
return x.max - x.min < C[i];
});
const ll fin = seg.prod().sum;
if (l == 0) {
res[i] = fin - seg.prod().min;
} else if (V[l - 1] > 0) {
const ll high = seg.prod(0, l).sum + seg.prod(l, Q).max;
res[i] = C[i] - (high - fin);
} else {
const ll low = seg.prod(0, l).sum + seg.prod(l, Q).min;
res[i] = fin - low;
}
for (const int q : disable[i]) {
seg.set(q, unit);
}
}
return res;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
468 KB |
Output is correct |
4 |
Correct |
1 ms |
468 KB |
Output is correct |
5 |
Correct |
3 ms |
564 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
367 ms |
36244 KB |
Output is correct |
2 |
Correct |
361 ms |
36260 KB |
Output is correct |
3 |
Correct |
379 ms |
36320 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
131 ms |
23256 KB |
Output is correct |
3 |
Correct |
73 ms |
14388 KB |
Output is correct |
4 |
Correct |
337 ms |
42148 KB |
Output is correct |
5 |
Correct |
351 ms |
42456 KB |
Output is correct |
6 |
Correct |
325 ms |
42944 KB |
Output is correct |
7 |
Correct |
366 ms |
42152 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
86 ms |
19216 KB |
Output is correct |
4 |
Correct |
66 ms |
13360 KB |
Output is correct |
5 |
Correct |
193 ms |
34244 KB |
Output is correct |
6 |
Correct |
168 ms |
34952 KB |
Output is correct |
7 |
Correct |
169 ms |
35620 KB |
Output is correct |
8 |
Correct |
202 ms |
34264 KB |
Output is correct |
9 |
Correct |
164 ms |
35680 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
468 KB |
Output is correct |
4 |
Correct |
1 ms |
468 KB |
Output is correct |
5 |
Correct |
3 ms |
564 KB |
Output is correct |
6 |
Correct |
367 ms |
36244 KB |
Output is correct |
7 |
Correct |
361 ms |
36260 KB |
Output is correct |
8 |
Correct |
379 ms |
36320 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
131 ms |
23256 KB |
Output is correct |
11 |
Correct |
73 ms |
14388 KB |
Output is correct |
12 |
Correct |
337 ms |
42148 KB |
Output is correct |
13 |
Correct |
351 ms |
42456 KB |
Output is correct |
14 |
Correct |
325 ms |
42944 KB |
Output is correct |
15 |
Correct |
366 ms |
42152 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
86 ms |
19216 KB |
Output is correct |
19 |
Correct |
66 ms |
13360 KB |
Output is correct |
20 |
Correct |
193 ms |
34244 KB |
Output is correct |
21 |
Correct |
168 ms |
34952 KB |
Output is correct |
22 |
Correct |
169 ms |
35620 KB |
Output is correct |
23 |
Correct |
202 ms |
34264 KB |
Output is correct |
24 |
Correct |
164 ms |
35680 KB |
Output is correct |
25 |
Correct |
1 ms |
212 KB |
Output is correct |
26 |
Correct |
68 ms |
13480 KB |
Output is correct |
27 |
Correct |
148 ms |
22880 KB |
Output is correct |
28 |
Correct |
305 ms |
40792 KB |
Output is correct |
29 |
Correct |
355 ms |
41168 KB |
Output is correct |
30 |
Correct |
315 ms |
41384 KB |
Output is correct |
31 |
Correct |
380 ms |
41496 KB |
Output is correct |
32 |
Correct |
322 ms |
41784 KB |
Output is correct |