#include "bits/stdc++.h"
using namespace std;
#define int long long
#ifdef Nero
#include "Deb.h"
#else
#define debug(...)
#endif
const int N = 2e5 + 5;
const long long INF = 1e15 + 15;
struct node {
long long sum, lazy, mn, mn2;
int mnc;
};
int ptr[N];
long long tree[N];
node beats[N * 2];
long long seg[N * 2];
long long lazy[N * 2];
node combine(node lx, node rx) {
node ret;
ret.lazy = 0;
ret.sum = lx.sum + rx.sum;
if (lx.mn == rx.mn) {
ret.mn = lx.mn;
ret.mnc = lx.mnc + rx.mnc;
ret.mn2 = min(lx.mn2, rx.mn2);
} else if (lx.mn < rx.mn) {
ret.mn = lx.mn;
ret.mnc = lx.mnc;
ret.mn2 = min(lx.mn2, rx.mn);
} else {
ret.mn = rx.mn;
ret.mnc = rx.mnc;
ret.mn2 = min(lx.mn, rx.mn2);
}
return ret;
}
void build_beats(int nd, int l, int r) {
if (l == r) {
beats[nd].mnc = 1;
beats[nd].mn2 = INF;
beats[nd].lazy = beats[nd].sum = beats[nd].mn = 0;
return;
}
int mid = (l + r) >> 1;
int rs = nd + ((mid - l + 1) << 1);
build_beats(nd + 1, l, mid);
build_beats(rs, mid + 1, r);
beats[nd] = combine(beats[nd + 1], beats[rs]);
}
void apply_add(int nd, int l, int r, int v) {
beats[nd].sum += (long long) (r - l + 1) * v;
beats[nd].mn += v;
if (beats[nd].mn2 != INF) {
beats[nd].mn2 += v;
}
beats[nd].lazy += v;
}
void apply_maximize(int nd, int l, int r, int v) {
if (beats[nd].mn >= v) {
return;
}
beats[nd].sum -= (long long) beats[nd].mn * beats[nd].mnc;
beats[nd].mn = v;
beats[nd].sum += (long long) beats[nd].mn * beats[nd].mnc;
}
void push_down(int nd, int l, int r) {
int mid = (l + r) >> 1;
int rs = nd + ((mid - l + 1) << 1);
apply_add(nd + 1, l, mid, beats[nd].lazy);
apply_add(rs, mid + 1, r, beats[nd].lazy);
beats[nd].lazy = 0;
apply_maximize(nd + 1, l, mid, beats[nd].mn);
apply_maximize(rs, mid + 1, r, beats[nd].mn);
}
void add_beats(int nd, int l, int r, int s, int e, int v) {
if (l >= s && r <= e) {
apply_add(nd, l, r, v);
return;
}
push_down(nd, l, r);
int mid = (l + r) >> 1;
int rs = nd + ((mid - l + 1) << 1);
if (mid >= e) {
add_beats(nd + 1, l, mid, s, e, v);
} else {
if (mid < s) {
add_beats(rs, mid + 1, r, s, e, v);
} else {
add_beats(nd + 1, l, mid, s, e, v);
add_beats(rs, mid + 1, r, s, e, v);
}
}
beats[nd] = combine(beats[nd + 1], beats[rs]);
}
void maximize(int nd, int l, int r, int s, int e, int v) {
if (beats[nd].mn >= v) {
return;
}
if (l >= s && r <= e && beats[nd].mn2 > v) {
apply_maximize(nd, l, r, v);
return;
}
push_down(nd, l, r);
int mid = (l + r) >> 1;
int rs = nd + ((mid - l + 1) << 1);
if (mid >= e) {
maximize(nd + 1, l, mid, s, e, v);
} else {
if (mid < s) {
maximize(rs, mid + 1, r, s, e, v);
} else {
maximize(nd + 1, l, mid, s, e, v);
maximize(rs, mid + 1, r, s, e, v);
}
}
beats[nd] = combine(beats[nd + 1], beats[rs]);
}
long long qry_beats(int nd, int l, int r, int p) {
if (l == r) {
return beats[nd].sum;
}
push_down(nd, l, r);
int mid = (l + r) >> 1;
int rs = nd + ((mid - l + 1) << 1);
if (p <= mid) {
return qry_beats(nd + 1, l, mid, p);
} else {
return qry_beats(rs, mid + 1, r, p);
}
}
void upd(int ind, int v) {
while (ind < N) {
tree[ind] += v;
ind += ind & -ind;
}
}
void upd(int l, int r, int v) {
upd(l, v);
upd(r + 1, -v);
}
long long qry(int ind) {
long long ret = 0;
while (ind) {
ret += tree[ind];
ind -= ind & -ind;
}
return ret;
}
void build(int nd, int l, int r, vector<vector<pair<long long, int>>>& qs) {
if (l == r) {
if (!qs[l].empty()) {
seg[nd] = qs[l][0].first;
} else {
seg[nd] = INF;
}
return;
}
int mid = (l + r) >> 1;
int rs = nd + ((mid - l + 1) << 1);
build(nd + 1, l, mid, qs);
build(rs, mid + 1, r, qs);
seg[nd] = min(seg[nd + 1], seg[rs]);
}
void push(int nd, int l, int r) {
seg[nd] += lazy[nd];
if (l != r) {
int mid = (l + r) >> 1;
int rs = nd + ((mid - l + 1) << 1);
lazy[nd + 1] += lazy[nd];
lazy[rs] += lazy[nd];
}
lazy[nd] = 0;
}
void upd(int nd, int l, int r, int s, int e, long long v) {
push(nd, l, r);
if (l >= s && r <= e) {
lazy[nd] = v;
push(nd, l, r);
return;
}
int mid = (l + r) >> 1;
int rs = nd + ((mid - l + 1) << 1);
if (mid >= e) {
upd(nd + 1, l, mid, s, e, v);
push(rs, mid + 1, r);
} else {
if (mid < s) {
upd(rs, mid + 1, r, s, e, v);
push(nd + 1, l, mid);
} else {
upd(nd + 1, l, mid, s, e, v);
upd(rs, mid + 1, r, s, e, v);
}
}
seg[nd] = min(seg[nd + 1], seg[rs]);
}
int get(int nd, int l, int r) {
push(nd, l, r);
if (l == r) {
return l;
}
int mid = (l + r) >> 1;
int rs = nd + ((mid - l + 1) << 1);
push(nd + 1, l, mid);
if (seg[nd + 1] <= 0) {
return get(nd + 1, l, mid);
}
return get(rs, mid + 1, r);
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, q;
cin >> n >> m >> q;
build_beats(0, 1, n);
vector<vector<pair<long long, int>>> qs(m + 1);
vector<int> type(q), lq(q), rq(q), cq(q), kq(q), a(q), b(q), ans(q);
for (int i = 0; i < q; ++i) {
cin >> type[i];
if (type[i] == 1) {
cin >> lq[i] >> rq[i] >> cq[i] >> kq[i];
upd(lq[i], rq[i], kq[i]);
add_beats(0, 1, n, lq[i], rq[i], kq[i]);
} else if (type[i] == 2) {
cin >> lq[i] >> rq[i] >> kq[i];
add_beats(0, 1, n, lq[i], rq[i], -kq[i]);
maximize(0, 1, n, lq[i], rq[i], 0);
} else {
cin >> a[i] >> b[i];
long long tot = qry(a[i]);
long long cur = qry_beats(0, 1, n, a[i]);
if (cur >= b[i]) {
qs[a[i]].push_back({tot - (cur - b[i]), i});
}
}
}
for (int i = 1; i <= m; ++i) {
sort(qs[i].begin(), qs[i].end());
}
build(0, 1, m, qs);
for (int i = 0; i < q; ++i) {
if (type[i] == 3) {
cout << ans[i] << '\n';
}
if (type[i] != 1) {
continue;
}
upd(0, 1, m, lq[i], rq[i], -kq[i]);
while (seg[0] <= 0) {
int ind = get(0, 1, m);
ans[qs[ind][ptr[ind]].second] = cq[i];
ptr[ind]++;
if (false && ptr[ind] < (int) qs[ind].size()) {
upd(0, 1, m, ind, ind, qs[ind][ptr[ind]].first - qs[ind][ptr[ind] - 1].first);
} else {
upd(0, 1, m, ind, ind, INF);
}
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
18268 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
18268 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
67 ms |
25288 KB |
Output is correct |
| 2 |
Correct |
64 ms |
28240 KB |
Output is correct |
| 3 |
Incorrect |
65 ms |
27980 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
30 ms |
71268 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
18268 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
64 ms |
25432 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
18268 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
18268 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
