#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
int C;
struct AINT {
int n;
vi Mi, Ma, Lz;
vi LzSet0, LzSet1;
AINT(int N) : n(N), Mi(4 * N, 0), Ma(4 * N, 0), Lz(4 * N, 0), LzSet0(4 * N, 0), LzSet1(4 * N, 0) {}
void prop0(int u, int s, int d) {
if(LzSet0[u]) {
Mi[u] = Ma[u] = Lz[u] = 0;
if(s != d) {
LzSet0[u << 1] = 1;
LzSet1[u << 1] = 0;
LzSet0[u << 1 | 1] = 1;
LzSet1[u << 1 | 1] = 0;
}
LzSet0[u] = 0;
}
if(LzSet1[u]) {
Mi[u] = Ma[u] = C;
Lz[u] = 0;
if(s != d) {
LzSet0[u << 1] = 0;
LzSet1[u << 1] = 1;
LzSet0[u << 1 | 1] = 0;
LzSet1[u << 1 | 1] = 1;
}
LzSet1[u] = 0;
}
}
void prop(int u, int s, int d) {
prop0(u, s, d);
if(Lz[u]) {
prop0(u << 1, s, (s + d) >> 1);
prop0(u << 1 | 1, ((s + d) >> 1) + 1, d);
Ma[u] += Lz[u];
Mi[u] += Lz[u];
Mi[u] = max(Mi[u], 0);
Ma[u] = max(Ma[u], 0);
Ma[u] = min(Ma[u], C);
Mi[u] = min(Mi[u], C);
if(s != d) {
Lz[u << 1] += Lz[u];
Lz[u << 1 | 1] += Lz[u];
}
Lz[u] = 0;
}
}
void update(int l, int r, int v, int u, int s, int d) {
prop(u, s, d);
if(r < s || d < l) return;
if(l <= s && d <= r) {
if(Ma[u] + v <= C && Mi[u] + v >= 0) {
Lz[u] += v;
prop(u, s, d);
return;
}
if(Ma[u] + v <= 0) {
LzSet0[u] = 1;
prop(u, s, d);
return;
}
if(Mi[u] + v >= C) {
LzSet1[u] = 1;
prop(u, s, d);
return;
}
if(s == d) {
Lz[u] += v;
prop(u, s, d);
return;
}
}
update(l, r, v, u << 1, s, (s + d) >> 1);
update(l, r, v, u << 1 | 1, ((s + d) >> 1) + 1, d);
Mi[u] = min(Mi[u << 1], Mi[u << 1 | 1]);
Ma[u] = max(Ma[u << 1], Ma[u << 1 | 1]);
}
void update(int l, int r, int v) {
update(l, r, v, 1, 0, n - 1);
}
int query(int p, int u, int s, int d) {
prop(u, s, d);
if(s == d) return Ma[u];
int mij = (s + d) / 2;
if(p <= mij) return query(p, u << 1, s, mij);
return query(p, u << 1 | 1, mij + 1, d);
}
int query(int p) { return query(p, 1, 0, n - 1); }
};
vi distribute_candies(vi c, vi l, vi r, vi v) {
int n = c.size(), q = l.size();
bool all_poz = true;
for(auto it : v)
if(it < 0) all_poz = false;
// if(n <= 2000 && q <= 2000) {
// vi A(n, 0);
// for(int i = 0; i < q; ++i) {
// for(int j = l[i]; j <= r[i]; ++j) {
// A[j] += v[i];
// A[j] = max(A[j], 0);
// A[j] = min(A[j], c[j]);
// }
// }
// return A;
// }
// if(all_poz) {
// vll S(n, 0);
// for(int i = 0; i < q; ++i) {
// S[l[i]] += v[i];
// if(r[i] + 1 < n) S[r[i] + 1] -= v[i];
// }
// for(int i = 1; i < n; ++i) {
// S[i] = S[i] + S[i - 1];
// }
// vi Re(n, 0);
// for(int i = 0; i < n; ++i) {
// Re[i] = min(S[i], (ll)c[i]);
// }
// return Re;
// }
/// presupun ca c e acelasi
C = c[0];
AINT Sol(n);
for(int i = 0; i < q; ++i) {
Sol.update(l[i], r[i], v[i]);
}
vi Re(n);
for(int i = 0; i < n; ++i) {
Re[i] = Sol.query(i);
}
return Re;
}
Compilation message
candies.cpp: In function 'vi distribute_candies(vi, vi, vi, vi)':
candies.cpp:109:10: warning: variable 'all_poz' set but not used [-Wunused-but-set-variable]
109 | bool all_poz = true;
| ^~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
237 ms |
23124 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Runtime error |
127 ms |
10324 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
