#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 2e5 + 1;
const long long INF = 1e18;
struct node {
long long sum;
long long lazy;
long long mncnt, mxcnt, mn0, mn1, mx0, mx1;
} st[4 * maxn];
#define tm ((tl + tr) >> 1)
#define lv ((v << 1) | 1)
#define rv (lv + 1)
void pull(int v) {
st[v].sum = st[lv].sum + st[rv].sum;
if(st[lv].mn0 == st[rv].mn0) {
st[v].mn0 = st[lv].mn0;
st[v].mncnt = st[lv].mncnt + st[rv].mncnt;
st[v].mn1 = min(st[lv].mn1, st[rv].mn1);
} else if(st[lv].mn0 < st[rv].mn0) {
st[v].mn0 = st[lv].mn0;
st[v].mncnt = st[lv].mncnt;
st[v].mn1 = min(st[lv].mn1, st[rv].mn0);
} else {
st[v].mn0 = st[rv].mn0;
st[v].mncnt = st[rv].mncnt;
st[v].mn1 = min(st[rv].mn1, st[lv].mn0);
}
if(st[lv].mx0 == st[rv].mx0) {
st[v].mx0 = st[lv].mx0;
st[v].mxcnt = st[lv].mxcnt + st[rv].mxcnt;
st[v].mx1 = max(st[lv].mx1, st[rv].mx1);
} else if(st[lv].mx0 > st[rv].mx0) {
st[v].mx0 = st[lv].mx0;
st[v].mxcnt = st[lv].mxcnt;
st[v].mx1 = max(st[lv].mx1, st[rv].mx0);
} else {
st[v].mx0 = st[rv].mx0;
st[v].mxcnt = st[rv].mxcnt;
st[v].mx1 = min(st[rv].mx1, st[lv].mx0);
}
}
void push_lazy(int v, int tl, int tr) {
if(!st[v].lazy) return;
st[lv].sum += st[v].lazy * (tm - tl + 1);
st[lv].mn0 += st[v].lazy;
st[lv].mn1 += st[v].lazy;
st[lv].mx0 += st[v].lazy;
st[lv].mx1 += st[v].lazy;
st[lv].lazy += st[v].lazy;
st[rv].sum += st[v].lazy * (tr - (tm + 1) + 1);
st[rv].mn0 += st[v].lazy;
st[rv].mn1 += st[v].lazy;
st[rv].mx0 += st[v].lazy;
st[rv].mx1 += st[v].lazy;
st[rv].lazy += st[v].lazy;
st[v].lazy = 0LL;
}
void push_range(int v) {
if(st[lv].mn0 < st[v].mn0) {
st[lv].sum -= st[lv].mncnt * (st[v].mn0 - st[lv].mn0);
st[lv].mn0 = st[v].mn0;
}
if(st[rv].mn0 < st[v].mn0) {
st[rv].sum -= st[rv].mncnt * (st[v].mn0 - st[rv].mn0);
st[rv].mn0 = st[v].mn0;
}
if(st[lv].mx0 > st[v].mx0) {
st[lv].sum -= st[lv].mxcnt * (st[lv].mx0 - st[v].mx0);
st[lv].mx0 = st[v].mx0;
}
if(st[rv].mx0 > st[v].mx0) {
st[rv].sum -= st[rv].mxcnt * (st[rv].mx0 - st[v].mx0);
st[rv].mx0 = st[v].mx0;
}
}
void st_add(int v, int tl, int tr, int l, int r, ll val) {
if(tr < l || tl > r) return;
if(l <= tl && tr <= r) {
st[v].sum += val * (tr - tl + 1);
st[v].mn0 += val;
st[v].mn1 += val;
st[v].mx0 += val;
st[v].mx1 += val;
st[v].lazy += val;
return;
}
push_lazy(v, tl, tr);
push_range(v);
st_add(lv, tl, tm, l, r, val);
st_add(rv, tm + 1, tr, l, r, val);
pull(v);
}
void st_max(int v, int tl, int tr, int l, int r, ll val) {
if(tr < l || tl > r || st[v].mn0 >= val) return;
if(l <= tl && tr <= r && st[v].mn1 > val) {
if(tl != tr) push_lazy(v, tl, tr);
st[v].sum -= st[v].mncnt * (st[v].mn0 - val);
st[v].mn0 = val;
st[v].mx0 = max(st[v].mx0, val);
return;
}
push_lazy(v, tl, tr);
push_range(v);
st_max(lv, tl, tm, l, r, val);
st_max(rv, tm + 1, tr, l, r, val);
pull(v);
}
void st_min(int v, int tl, int tr, int l, int r, ll val) {
if(tr < l || tl > r || st[v].mx0 <= val) return;
if(l <= tl && tr <= r && st[v].mx1 < val) {
if(tl != tr) push_lazy(v, tl, tr);
st[v].sum -= st[v].mxcnt * (st[v].mx0 - val);
st[v].mx0 = val;
st[v].mn0 = min(st[v].mx0, val);
return;
}
push_lazy(v, tl, tr);
push_range(v);
st_min(lv, tl, tm, l, r, val);
st_min(rv, tm + 1, tr, l, r, val);
pull(v);
}
long long st_query(int v, int tl, int tr, int l, int r) {
if(tr < l || tl > r) return 0LL;
if(l <= tl && tr <= r) return st[v].sum;
push_lazy(v, tl, tr);
push_range(v);
return st_query(lv, tl, tm, l, r) + st_query(rv, tm + 1, tr, l, r);
}
void build(int v, int tl, int tr) {
if(tl == tr) {
st[v].lazy = st[v].sum = st[v].mn0 = st[v].mx0 = 0;
st[v].mx1 = -INF;
st[v].mn1 = INF;
st[v].mxcnt = st[v].mncnt = 1;
return;
}
build(lv, tl, tm);
build(rv, tm + 1, tr);
pull(v);
st[v].lazy = 0;
}
vector<int> distribute_candies(vector<int> C, vector<int> L, vector<int> R, vector<int> V) {
int N = C.size();
int Q = L.size();
build(0, 0, N - 1);
for(int i = 0; i < Q; ++i) {
st_add(0, 0, N - 1, L[i], R[i], V[i]);
st_min(0, 0, N - 1, L[i], R[i], (ll)C[0]);
st_max(0, 0, N - 1, L[i], R[i], 0LL);
}
vector<int> ans;
for(int i = 0; i < N; ++i) {
ans.push_back(st_query(0, 0, N - 1, i, i));
}
return ans;
}
/*
int32_t main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, Q; cin >> N >> Q;
build(0, 0, N - 1);
for(int i = 0; i < N; ++i) {
long long x; cin >> x;
st_add(0, 0, N - 1, i, i, x);
}
while(Q--) {
int t, l, r; cin >> t >> l >> r;
--r;
if(t == 3) {
cout << st_query(0, 0, N - 1, l, r) << '\n';
} else {
long long y; cin >> y;
if(t == 0) st_min(0, 0, N - 1, l, r, y);
else if(t == 1) st_max(0, 0, N - 1, l, r, y);
else st_add(0, 0, N - 1, l, r, y);
}
}
}*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 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 |
524 ms |
40576 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 |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
