#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
#define pb push_back
#define fi first
#define se second
#define debug(x) cout << #x << " => " << x << "\n";
const long long mod = 1e9 + 7;
int n, m, q;
struct Query {
int t;
int l, r, k, c, a, b;
} query[250005];
int itr;
pair <int,int> idx[250005];
vector <pair<int,int>> idxs[250005];
pair <int,int> a[250005];
int iitr, le[250005], ri[250005];
int ans[250005];
struct SegTree {
int tree[1000005], lazy[1000005];
void push(int idx, int l, int r) {
if(lazy[idx] != 0) {
tree[idx] += lazy[idx];
if(l != r) {
lazy[idx * 2] += lazy[idx];
lazy[idx * 2] = max(lazy[idx * 2], -tree[idx * 2]);
lazy[idx * 2 + 1] += lazy[idx];
lazy[idx * 2 + 1] = max(lazy[idx * 2 + 1], -tree[idx * 2 + 1]);
}
lazy[idx] = 0;
}
}
void add(int idx, int l, int r, int x, int y, int v) {
push(idx, l, r);
if(l > r || l > y || r < x) return;
if(l >= x && r <= y) {
lazy[idx] += v;
lazy[idx] = max(lazy[idx], -tree[idx]);
push(idx, l, r);
return;
}
int mid = (l + r) / 2;
add(idx * 2, l, mid, x, y, v);
add(idx * 2 + 1, mid + 1, r, x, y, v);
tree[idx] = max(tree[idx * 2], tree[idx * 2 + 1]);
}
int query(int idx, int l, int r, int x) {
push(idx, l, r);
if(l == r) return tree[idx];
int mid = (l + r) / 2;
if(x <= mid) return query(idx * 2, l, mid, x);
else return query(idx * 2 + 1, mid + 1, r, x);
}
} cur, tot;
struct SegTree2 {
int tree[1000005], lazy[1000005];
void push(int idx, int l, int r) {
if(lazy[idx] != 0) {
tree[idx] += lazy[idx];
if(l != r) {
lazy[idx * 2] += lazy[idx];
lazy[idx * 2 + 1] += lazy[idx];
}
lazy[idx] = 0;
}
}
void add(int idx, int l, int r, int x, int y, int v) {
push(idx, l, r);
if(l > r || l > y || r < x) return;
if(l >= x && r <= y) {
lazy[idx] += v;
push(idx, l, r);
return;
}
int mid = (l + r) / 2;
add(idx * 2, l, mid, x, y, v);
add(idx * 2 + 1, mid + 1, r, x, y, v);
tree[idx] = min(tree[idx * 2], tree[idx * 2 + 1]);
}
int query(int idx, int l, int r) {
push(idx, l, r);
if(tree[idx] > 0) return -1;
if(l == r) {tree[idx] = 1e18; return l;}
int mid = (l + r) / 2;
push(idx * 2, l, mid);
push(idx * 2 + 1, mid + 1, r);
int res = -1;
if(tree[idx * 2] <= 0) res = query(idx * 2, l, mid);
else res = query(idx * 2 + 1, mid + 1, r);
tree[idx] = min(tree[idx * 2], tree[idx * 2 + 1]);
push(idx, l, r);
return res;
}
int val(int idx, int l, int r, int x) {
push(idx, l, r);
if(l == r) return tree[idx];
int mid = (l + r) / 2;
if(x <= mid) return val(idx * 2, l, mid, x);
else return val(idx * 2 + 1, mid + 1, r, x);
}
} group;
void solve () {
cin >> n >> m >> q;
for(int i = 1; i <= q; i++) {
cin >> query[i].t;
if(query[i].t == 1) {
cin >> query[i].l >> query[i].r >> query[i].c >> query[i].k;
cur.add(1, 1, n, query[i].l, query[i].r, query[i].k);
tot.add(1, 1, n, query[i].l, query[i].r, query[i].k);
}
else if(query[i].t == 2) {
cin >> query[i].l >> query[i].r >> query[i].k;
cur.add(1, 1, n, query[i].l, query[i].r, -query[i].k);
}
else {
cin >> query[i].a >> query[i].b;
int Total = tot.query(1, 1, n, query[i].a);
int Cur = cur.query(1, 1, n, query[i].a);
if(query[i].b <= Cur) idx[++itr] = {Total - Cur + query[i].b, query[i].a};
else idx[++itr] = {-1, query[i].a};
}
}
// for(int i = 1; i <= itr; i++)
// cout << idx[i].fi << "\n";
for(int i = 1; i <= itr; i++)
idxs[idx[i].se].pb({idx[i].fi, i});
for(int i = 1; i <= n; i++) {
sort(idxs[i].begin(), idxs[i].end());
le[i] = iitr + 1;
for(auto j : idxs[i]) a[++iitr] = j;
ri[i] = iitr;
}
assert(itr == iitr);
for(int i = 1; i <= itr; i++) {
group.add(1, 1, itr, i, i, a[i].fi);
}
for(int i = 1; i <= q; i++) {
if(query[i].t == 1) {
group.add(1, 1, itr, le[query[i].l], ri[query[i].r], -query[i].k);
while (true) {
int aqua = group.query(1, 1, itr);
if(aqua == -1) break;
ans[a[aqua].se] = query[i].c;
break;
}
}
}
for(int i = 1; i <= itr; i++)
if(idx[i].fi == -1) ans[i] = 0;
for(int i = 1; i <= itr; i++)
cout << ans[i] << "\n";
}
signed main () {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
solve ();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
6612 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
6612 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
78 ms |
18568 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
567 ms |
53540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
6612 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
109 ms |
19088 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
6612 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
6612 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
