#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll inf = 1e18;
vector<ll> mn, mn2, mx, mx2, lzad, lzmn, lzmx;
void apply_add(int p, ll v) {
if (p >= mn.size()) {
return;
}
lzad[p] += v;
mn[p] += v;
mx[p] += v;
if (mn2[p] != inf) {
mn2[p] += v;
}
if (mx2[p] != -inf) {
mx2[p] += v;
}
}
void apply_min(int p, ll v) {
if (p >= mn.size()) {
return;
}
if (mn[p] == mx[p]) {
if (v < mn[p]) {
mn[p] = mx[p] = v;
lzmn[p] = v;
}
} else if (mx2[p] < v && v < mx[p]) {
mx[p] = v;
lzmn[p] = v;
}
}
void apply_max(int p, ll v) {
if (p >= mn.size()) {
return;
}
if (mn[p] == mx[p]) {
if (v > mn[p]) {
mn[p] = mx[p] = v;
lzmx[p] = v;
}
} else if (mn[p] < v && v < mn2[p]) {
mn[p] = v;
lzmx[p] = v;
}
}
void push_add(int p) {
apply_add(p * 2, lzad[p]);
apply_add(p * 2 + 1, lzad[p]);
lzad[p] = 0;
}
void push_min(int p) {
apply_min(p * 2, lzmn[p]);
apply_min(p * 2 + 1, lzmn[p]);
lzmn[p] = inf;
}
void push_max(int p) {
apply_max(p * 2, lzmx[p]);
apply_max(p * 2 + 1, lzmx[p]);
lzmx[p] = -inf;
}
void pull(int p) {
int l = p * 2;
int r = p * 2 + 1;
mx[p] = max(mx[l], mx[r]);
mn[p] = min(mn[l], mn[r]);
mx2[p] = max(mx[p] == mx[l] ? mx2[l] : mx[l], mx[p] == mx[r] ? mx2[r] : mx[r]);
mn2[p] = min(mn[p] == mn[l] ? mn2[l] : mn[l], mn[p] == mn[r] ? mn2[r] : mn[r]);
}
void add(int p, int l, int r, int L, int R, int v) {
push_add(p);
push_min(p);
push_max(p);
if (R <= l || r <= L) {
return;
}
if (L <= l && r <= R) {
apply_add(p, v);
return;
}
int m = (l + r + 1) / 2;
add(p * 2, l, m, L, R, v);
add(p * 2 + 1, m, r, L, R, v);
pull(p);
}
void upd(int p, int l, int r, int L, int R, ll v, bool f) {
push_add(p);
push_min(p);
push_max(p);
if (R <= l || r <= L || (!f && v >= mx[p]) || (f && v <= mn[p])) {
return;
}
if (L <= l && r <= R && (mn[p] == mx[p] || (!f && v > mx2[p]) || (f && v < mn2[p]))) {
if (f) {
apply_max(p, v);
} else {
apply_min(p, v);
}
return;
}
int m = (l + r + 1) / 2;
upd(p * 2, l, m, L, R, v, f);
upd(p * 2 + 1, m, r, L, R, v, f);
pull(p);
}
vector<int> distribute_candies(vector<int> C, vector<int> L, vector<int> R, vector<int> V) {
int N = C.size(), Q = V.size();
int M = 2 << __lg(N - 1);
mn.resize(2 * M, 0);
mx.resize(2 * M, 0);
mn2.resize(2 * M, inf);
mx2.resize(2 * M, -inf);
lzad.resize(2 * M);
lzmn.resize(2 * M, inf);
lzmx.resize(2 * M, -inf);
for (int i = 0; i < Q; i++) {
add(1, 0, M, L[i], R[i] + 1, V[i]);
if (V[i] > 0) {
upd(1, 0, M, L[i], R[i] + 1, C[0], 0);
} else {
upd(1, 0, M, L[i], R[i] + 1, 0, 1);
}
}
for (int i = 1; i < M; i++) {
int cnt = 0;
cnt += lzad[i] != 0;
cnt += lzmn[i] != inf;
cnt += lzmx[i] != -inf;
assert(cnt <= 1);
push_add(i);
push_min(i);
push_max(i);
}
vector<int> ans(N);
for (int i = 0; i < N; i++) {
ans[i] = mx[i + M];
}
return ans;
}
Compilation message
candies.cpp: In function 'void apply_add(int, ll)':
candies.cpp:8:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
8 | if (p >= mn.size()) {
| ~~^~~~~~~~~~~~
candies.cpp: In function 'void apply_min(int, ll)':
candies.cpp:22:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
22 | if (p >= mn.size()) {
| ~~^~~~~~~~~~~~
candies.cpp: In function 'void apply_max(int, ll)':
candies.cpp:36:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
36 | if (p >= mn.size()) {
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1240 ms |
76268 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
596 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
