#include "candies.h"
#include<bits/stdc++.h>
using namespace std;
#define in insert
#define all(x) x.begin(),x.end()
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second
// #define int long long
typedef long long ll;
typedef vector<int> vi;
typedef set<int> si;
typedef multiset<int> msi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
const int mxn = 2e5 + 10;
const long long inf = 1e18 + 10;
struct segTreeBeats {
struct node {
long long mx1, mx2, mn1, mn2, lz, mxc, mnc, sum;
node(int x) : mx1(x), mx2(-inf), mn1(x), mn2(inf), lz(0), mxc(1), mnc(1), sum(x) {}
node() {}
node operator+(const node& a) {
node ret;
ret.mx1 = max(a.mx1, mx1);
ret.mn1 = min(a.mn1, mn1);
ret.sum = a.sum + sum;
if(mx1 == a.mx1) {
ret.mxc = a.mxc + mxc;
ret.mx2 = max(a.mx2, mx2);
} else {
if(mx1 > a.mx1) {
ret.mxc = mxc;
ret.mx2 = max(a.mx1, mx2);
} else {
ret.mxc = a.mxc;
ret.mx2 = max(a.mx2, mx1);
}
}
if(mn1 == a.mn1) {
ret.mnc = a.mnc + mnc;
ret.mn2 = min(a.mn2, mn2);
} else {
if(mn1 < a.mn1) {
ret.mnc = mnc;
ret.mn2 = min(a.mn1, mn2);
} else {
ret.mnc = a.mnc;
ret.mn2 = min(a.mn2, mn1);
}
}
return ret;
}
};
vector<node> d;
vector<int> c;
int n;
void build(int l, int r, int i) {
if(l == r) {
d[i] = c[l];
return;
}
int m = (l + r) / 2;
build(l, m, i * 2);
build(m + 1, r, i * 2 + 1);
d[i] = d[i * 2] + d[i * 2 + 1];
}
segTreeBeats(int _n, vector<int> _c) {
n = _n;
c = _c;
d.resize(n * 4 + 10);
build(0, n - 1, 1);
}
void add(int i, int l, int r, long long v) {
d[i].sum += 1LL * v * (r - l + 1);
d[i].mx1 += v; d[i].mn1 += v;
if(d[i].mx2 != -inf) d[i].mx2 += v;
if(d[i].mn2 != inf) d[i].mn2 += v;
d[i].lz += v;
}
void mnn(int i, int l, int r, long long v) {
d[i].sum -= 1LL * (r - l + 1) * d[i].mx1;
d[i].mx1 = v;
if(d[i].mn1 > v) d[i].mn1 = v;
else if(d[i].mn2 > v) d[i].mn2 = v;
d[i].sum += 1LL * (r - l + 1) * d[i].mx1;
}
void mxx(int i, int l, int r, long long v) {
d[i].sum -= 1LL * (r - l + 1) * d[i].mn1;
d[i].mn1 = v;
if(d[i].mx1 < v) d[i].mx1 = v;
else if(d[i].mx2 < v) d[i].mx2 = v;
d[i].sum += 1LL * (r - l + 1) * d[i].mn1;
}
void pro(int i, int l, int r) {
if(l == r) return;
int m = (l + r) / 2;
add(i * 2, l, m, d[i].lz);
add(i * 2 + 1, m + 1, r, d[i].lz);
d[i].lz = 0;
mnn(i * 2, l, m, d[i].mn1);
mnn(i * 2 + 1, m + 1, r, d[i].mn1);
mxx(i * 2, l, m, d[i].mx1);
mxx(i * 2 + 1, m + 1, r, d[i].mx1);
}
void add(int l, int r, int i, int x, int y, long long v) {
if(l >= x && r <= y) {
add(i, l, r, v);
return;
}
pro(i, l, r);
int m = (l + r) / 2;
if(x <= m) add(l, m, i * 2, x, y, v);
if(y > m) add(m + 1, r, i * 2 + 1, x, y, v);
d[i] = d[i * 2] + d[i * 2 + 1];
}
void mnn(int l, int r, int i, int x, int y, long long v) {
if(d[i].mx1 <= v) return;
if(l >= x && r <= y && d[i].mx2 < v) {
mnn(i, l, r, v);
return;
}
pro(i, l, r);
int m = (l + r) / 2;
if(x <= m) mnn(l, m, i * 2, x, y, v);
if(y > m) mnn(m + 1, r, i * 2 + 1, x, y, v);
d[i] = d[i * 2] + d[i * 2 + 1];
}
void mxx(int l, int r, int i, int x, int y, long long v) {
if(d[i].mn1 >= v) return;
if(l >= x && r <= y && d[i].mn2 > v) {
mxx(i, l, r, v);
return;
}
pro(i, l, r);
int m = (l + r) / 2;
if(x <= m) mxx(l, m, i * 2, x, y, v);
if(y > m) mxx(m + 1, r, i * 2 + 1, x, y, v);
d[i] = d[i * 2] + d[i * 2 + 1];
}
void add(int l, int r, long long v) {
add(0, n - 1, 1, l, r, v);
}
void mnn(int l, int r, long long v) {
mnn(0, n - 1, 1, l, r, v);
}
void mxx(int l, int r, long long v) {
mxx(0, n - 1, 1, l, r, v);
}
long long getSum(int l, int r, int i, int x, int y) {
if(l >= x && r <= y) return d[i].sum;
if(l > y || r < x) return 0LL;
int m = (l + r) / 2;
pro(i, l, r);
return getSum(l, m, i * 2, x, y) + getSum(m + 1, r, i * 2 + 1, x, y);
}
long long getSum(int l, int r) {
return getSum(0, n - 1, 1, l, r);
}
};
vi distribute_candies(vi c, vi l, vi r, vi v) {
int n = c.size(), q = l.size();
vector<long long> ret(n);
if(n * q <= 2000 * 2000) {
for(int i = 0; i < q; i++) {
for(int j = l[i]; j <= r[i]; j++) {
ret[j] += v[i];
ret[j] = min(1ll * c[j], max(0ll, ret[j]));
}
}
return vector<int>(all(ret));
}
if(*min_element(all(v)) >= 0) {
for(int i = 0; i < q; i++) {
ret[l[i]] += v[i];
if(r[i] + 1 < n) ret[r[i] + 1] -= v[i];
}
for(int i = 1; i < n; i++) {
ret[i] += ret[i - 1];
}
for(int i = 0; i < n; i++) {
ret[i] = min(1ll * c[i], max(0ll, ret[i]));
}
return vector<int>(all(ret));
}
if(*max_element(all(c)) == *min_element(all(c))) {
segTreeBeats st(n, c);
for(int i = 0; i < q; i++) {
st.add(l[i], r[i], v[i]);
st.mnn(l[i], r[i], c[0]);
st.mxx(l[i], r[i], 0);
}
for(int i = 0; i < n; i++) {
ret[i] = st.getSum(i, i);
}
return vector<int>(all(ret));
}
return vector<int>(all(ret));
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 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 |
3 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
93 ms |
8808 KB |
Output is correct |
| 2 |
Correct |
85 ms |
8900 KB |
Output is correct |
| 3 |
Correct |
91 ms |
8808 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Runtime error |
54 ms |
10572 KB |
Execution killed with signal 11 |
| 3 |
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 |
Incorrect |
44 ms |
4964 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 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 |
3 ms |
340 KB |
Output is correct |
| 6 |
Correct |
93 ms |
8808 KB |
Output is correct |
| 7 |
Correct |
85 ms |
8900 KB |
Output is correct |
| 8 |
Correct |
91 ms |
8808 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Runtime error |
54 ms |
10572 KB |
Execution killed with signal 11 |
| 11 |
Halted |
0 ms |
0 KB |
- |
