#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2.5e5;
namespace ST {
ll mn[4 * N], s_mn[4 * N], upd[4 * N], upd_mn[4 * N];
int cnt[4 * N];
void apply(int node, ll x) {
mn[node] += x;
s_mn[node] += x;
upd_mn[node] += x;
upd[node] += x;
}
void apply_mn(int node, ll x) {
upd_mn[node] = max(upd_mn[node], x);
mn[node] = max(mn[node], upd_mn[node]);
}
void push(int node) {
apply(node << 1, upd[node]);
apply(node << 1 | 1, upd[node]);
apply_mn(node << 1, upd_mn[node]);
apply_mn(node << 1 | 1, upd_mn[node]);
upd[node] = 0;
upd_mn[node] = -1e17;
}
void pull(int node) {
mn[node] = min(mn[node << 1], mn[node << 1 | 1]);
cnt[node] = 0;
if (mn[node << 1] == mn[node]) cnt[node] += cnt[node << 1];
if (mn[node << 1 | 1] == mn[node]) cnt[node] += cnt[node << 1 | 1];
s_mn[node] = 1e17;
for (auto x : {mn[node << 1], s_mn[node << 1], mn[node << 1 | 1], s_mn[node << 1 | 1]}) {
if (x != mn[node]) s_mn[node] = min(s_mn[node], x);
}
}
void update(int ql, int qr, int x, int node = 1, int l = 0, int r = N - 1) {
if (r < ql || qr < l) return;
if (ql <= l && r <= qr) {
// cout << 11 << ' ' << node << ' ' << l << ' ' << r << ' ' << ql << ' ' << qr << ' ' << x << ' ' << mn[node] << ' ' << s_mn[node] << ' ' << cnt[node] << endl;
apply(node, x);
// cout << l << ' ' << r << ' ' << mn[node] << ' ' << s_mn[node] << ' ' << cnt[node] << endl;
return;
}
// cout << node << ' ' << l << ' ' << r << ' ' << mn[node] << ' ' << s_mn[node] << ' ' << cnt[node] << endl;
push(node);
int m = (l + r) / 2;
update(ql, qr, x, node << 1, l, m);
update(ql, qr, x, node << 1 | 1, m + 1, r);
pull(node);
// cout << l << ' ' << r << ' ' << mn[node] << ' ' << s_mn[node] << ' ' << cnt[node] << endl;
}
void fix(int node = 1, int l = 0, int r = N - 1) {
// cout << l << ' ' << r << ' ' << mn[node] << ' ' << s_mn[node] << ' ' << cnt[node] << endl;
if (mn[node] >= 0) return;
if (s_mn[node] > 0) {
apply_mn(node, 0);
// cout << 11 << ' ' << l << ' ' << r << ' ' << mn[node] << ' ' << s_mn[node] << ' ' << cnt[node] << endl;
return;
}
push(node);
int m = (l + r) / 2;
fix(node << 1, l, m);
fix(node << 1 | 1, m + 1, r);
pull(node);
// cout << l << ' ' << r << ' ' << mn[node] << ' ' << s_mn[node] << ' ' << cnt[node] << endl;
}
ll get(int k, int node = 1, int l = 0, int r = N - 1) {
if (l == r) return mn[node];
push(node);
int m = (l + r) / 2;
if (k <= m) return get(k, node << 1, l, m);
else return get(k, node << 1 | 1, m + 1, r);
}
void build(int node = 1, int l = 0, int r = N - 1) {
if (l == r) {
mn[node] = 0;
cnt[node] = 1;
s_mn[node] = 1e17;
upd[node] = 0;
upd_mn[node] = -1e17;
} else {
int m = (l + r) / 2;
build(node << 1, l, m);
build(node << 1 | 1, m + 1, r);
pull(node);
}
}
}
const int B = 500;
vector<int> t_block[B], t_elem[B];
vector<ll> pref_block[N], pref_elem[N];
int col[N];
int main() {
cin.tie(nullptr)->sync_with_stdio(0);
for (int i = 0; i < B; ++i) pref_block[i] = {0};
for (int i = 0; i < N; ++i) pref_elem[i] = {0};
ST::build();
int n, m, q;
cin >> n >> m >> q;
for (int i = 0; i < q; ++i) {
int t;
cin >> t;
if (t == 1) {
int l, r;
ll b;
cin >> l >> r >> col[i] >> b;
--l, --r;
ST::update(l, r, b);
for (; l <= r; l++) {
if (l % B == 0 && l + B - 1 <= r) {
t_block[l / B].push_back(i);
pref_block[l / B].push_back(pref_block[l / B].back() + b);
l += B - 1;
} else {
t_elem[l].push_back(i);
pref_elem[l].push_back(pref_elem[l].back() + b);
}
}
} else if (t == 2) {
int l, r;
ll k;
cin >> l >> r >> k;
--l, --r;
ST::update(l, r, -k);
ST::fix();
} else {
int a;
ll b;
cin >> a >> b;
--a;
ll all = ST::get(a);
// cerr << a << ' ' << all << endl;
if (b > all) {
cout << "0\n";
continue;
}
b = all - b + 1;
// cerr << i << ' ' << a << ' ' << b << endl;
int L = -1, R = i;
while (R - L > 1) {
int M = (L + R) / 2;
ll s_block = pref_block[a / B].back() - pref_block[a / B][upper_bound(t_block[a / B].begin(), t_block[a / B].end(), M) - t_block[a / B].begin()];
// cerr << s_block << endl;
ll s_elem = pref_elem[a].back() - pref_elem[a][upper_bound(t_elem[a].begin(), t_elem[a].end(), M) - t_elem[a].begin()];
if (s_block + s_elem >= b) L = M;
else R = M;
}
cout << col[R] << '\n';
}
// cerr << i << endl;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
62 ms |
95528 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
62 ms |
95528 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
55 ms |
95624 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
57 ms |
95872 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
62 ms |
95528 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
64 ms |
95656 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
62 ms |
95528 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
62 ms |
95528 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
