#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_upd(int p, ll cmn, ll cmx) {
if (p >= mn.size()) {
return;
}
assert(cmn >= cmx);
if (mn[p] == mx[p]) {
if (cmn < mn[p]) {
mn[p] = mx[p] = cmn;
lzmn[p] = cmn;
}
if (cmx > mx[p]) {
mx[p] = mn[p] = cmx;
lzmx[p] = cmx;
}
return;
}
if (cmn > mx2[p] && cmn < mx[p]) {
mx[p] = cmn;
lzmn[p] = cmn;
}
if (cmx < mn2[p] && cmx > mn[p]) {
mn[p] = cmx;
lzmx[p] = cmx;
}
}
void push_add(int p) {
apply_add(p * 2, lzad[p]);
apply_add(p * 2 + 1, lzad[p]);
lzad[p] = 0;
}
void push_upd(int p) {
apply_upd(p * 2, lzmn[p], lzmx[p]);
apply_upd(p * 2 + 1, lzmn[p], lzmx[p]);
lzmn[p] = inf;
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_upd(p);
if (R <= l || r <= L) {
return;
}
if (L <= l && r <= R) {
apply_add(p, v);
return;
}
int m = (l + r + 1) / 2;
push_add(p);
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);
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_upd(p, inf, v);
} else {
apply_upd(p, v, -inf);
}
return;
}
int m = (l + r + 1) / 2;
push_upd(p);
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++) {
push_add(i);
push_upd(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_upd(int, ll, 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()) {
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1323 ms |
36092 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
