#include<bits/stdc++.h>
#ifndef LOCAL
#define cerr if(false)cerr
#endif // LOCAL
using namespace std;
using ll = long long;
const int N = 25e4 + 66;
int t[N], l[N], r[N], c[N], A[N], n;
ll k[N], B[N];
pair<ll,ll>f[N << 2];
ll del[N];
const int inf = 1e9;
void delpush(int v, int l, int r) {
if (f[v] == pair{0ll, 0ll}) return;
if (r - l == 1) del[l] = max(del[l] - f[v].first, f[v].second);
else {
f[v << 1] = {f[v << 1].first + f[v].first, max(f[v << 1].second - f[v].first,
f[v].second)};
f[v<<1|1] = {f[v<<1|1].first + f[v].first, max(f[v<<1|1].second - f[v].first,
f[v].second)};
}
f[v] = {0ll, 0ll};
}
void delupd(int L, int R, pair<ll,ll> add, int l = 0, int r = n, int v = 1) {
delpush(v, l, r);
if (L <= l && r <= R) {
f[v] = add;
delpush(v, l, r);
return;
}
if (L >= r || l >= R) {
return;
}
int m = (l + r) >> 1;
delupd(L, R, add, l, m, v << 1);
delupd(L, R, add, m, r, v<<1|1);
}
ll delget(int pos, int l = 0, int r = n, int v = 1) {
delpush(v, l, r);
if (r - l == 1) return del[l];
int m = (l + r) >> 1;
if (pos < m) return delget(pos, l, m, v << 1);
else return delget(pos, m, r, v<<1|1);
}
ll ans[N];
ll tall[N];
void allupd(int pos, ll v) {
while (pos < N) { tall[pos] += v, pos |= pos + 1; }
}
ll allget(int pos) { ll r = 0; while (pos >= 0) { r += tall[pos], pos &= pos + 1, --pos; }
return r;}
ll mx[N << 2], q[N << 2];
const ll INF = 1e18;
vector<int>qs[N];
void push(int v, int l, int r) {
if (q[v] == 0) return;
mx[v] += q[v];
if (r - l > 1) q[v << 1] += q[v], q[v<<1|1] += q[v];
q[v] = 0;
}
void upd(int L, int R, ll V, int l = 0, int r = n, int v = 1) {
push(v, l, r);
if (L <= l && r <= R) {
q[v] += V;
push(v, l, r);
return;
}
if (L >= r || l >= R) {
return;
}
int m = (l + r) >> 1;
upd(L, R, V, l, m, v << 1);
upd(L, R, V, m, r, v<<1|1);
mx[v] = max(mx[v << 1], mx[v<<1|1]);
}
int get(int l = 0, int r = n, int v = 1) {
if (v == 1) push(v, l, r);
if (mx[v] < 0) return n;
if (r - l == 1) return l;
int m = (l + r) >> 1;
push(v << 1, l, m);
if (mx[v << 1] >= 0) return get(l, m, v << 1);
return get(m, r, v<<1|1);
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int m, q;
cin >> n >> m >> q;
for (int i = 0 ; i < q ; ++ i) {
cin >> t[i];
if (t[i] == 1) {
cin >> l[i] >> r[i] >> c[i] >> k[i];
--l[i];
delupd(l[i], r[i], {-k[i], -inf});
allupd(l[i], k[i]);
allupd(r[i], -k[i]);
} else if (t[i] == 2) {
cin >> l[i] >> r[i] >> k[i];
--l[i];
delupd(l[i], r[i], {k[i], 0});
} else {
cin >> A[i] >> B[i];
--A[i];
ll all = allget(A[i]);
ll cur = delget(A[i]);
ans[i] = 0;
if (B[i] <= cur) {
B[i] += all - cur;
qs[A[i]].emplace_back(i);
}
}
}
vector<int>inds(n);
for (int i = 0 ; i < n ; ++ i) {
if (qs[i].empty()) {
upd(i, i + 1, -INF);
continue;
}
sort(qs[i].begin(), qs[i].end(), [](int a, int b) {
return B[a] < B[b];
});
upd(i, i + 1, -B[qs[i][0]]);
}
for (int i = 0 ; i < q ; ++ i) {
if (t[i] == 1) {
upd(l[i], r[i], k[i]);
while (1) {
int j = get();
if (j == n) break;
ans[qs[j][inds[j]]] = c[i];
inds[j]++;
if (inds[j] < (int)qs[j].size()) {
upd(j, j + 1, -B[qs[j][inds[j]]] + B[qs[j][inds[j] - 1]]);
} else {
upd(j, j + 1, -INF);
}
}
}
}
for (int i = 0 ; i < q ; ++ i) {
if (t[i] == 3) {
cout << ans[i] << "\n";
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
6636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
6636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
113 ms |
15596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
619 ms |
39840 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
6636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
129 ms |
16236 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
6636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
6636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
