#include "bits/stdc++.h"
using namespace std;
#define ar array
#define int long long
const int N = 25e4 + 5;
struct node{
int t, l, r, c, k, a, b;
};
struct BIT{
int tree[N<<2], p[2][N<<2];
void push(int x, int lx, int rx){
if(lx == rx) return;
tree[x<<1] += p[0][x], tree[x<<1|1] += p[0][x];
p[0][x<<1] += p[0][x], p[0][x<<1|1] += p[0][x];
p[1][x<<1] += p[0][x], p[1][x<<1|1] += p[0][x];
tree[x<<1] = max(tree[x<<1], p[1][x]);
p[1][x<<1] = max(p[1][x<<1], p[1][x]);
p[0][x<<1] = max(p[0][x<<1], p[1][x]);
tree[x<<1|1] = max(tree[x<<1|1], p[1][x]);
p[1][x<<1|1] = max(p[1][x<<1|1], p[1][x]);
p[0][x<<1|1] = max(p[0][x<<1|1], p[1][x]);
p[0][x] = 0, p[1][x] = -1e18;
}
void add(int l, int r, int v, int lx = 0, int rx = N, int x = 1){
if(lx > r || rx < l) return;
push(x, lx, rx);
if(lx >= l && rx <= r){
tree[x] += v;
p[0][x] += v, p[1][x] += v;
return;
} int m = (lx + rx) >> 1;
add(l, r, v, lx, m, x<<1),
add(l, r, v, m+1, rx, x<<1|1);
tree[x] = max(tree[x<<1], tree[x<<1|1]);
}
void umax(int l, int r, int v, int lx = 0, int rx = N, int x = 1){
if(lx > r || rx < l) return;
push(x, lx, rx);
if(lx >= l && rx <= r){
tree[x] = max(tree[x], v);
p[1][x] = max(p[1][x], v);
return;
} int m = (lx + rx) >> 1;
umax(l, r, v, lx, m, x<<1),
umax(l, r, v, m+1, rx, x<<1|1);
tree[x] = max(tree[x<<1], tree[x<<1|1]);
}
int get(int i, int lx = 0, int rx = N, int x = 1){
if(lx == rx) return tree[x];
push(x, lx, rx);
int m = (lx + rx) >> 1;
if(i <= m) return get(i, lx, m, x<<1);
else return get(i, m+1, rx, x<<1|1);
}
}cur, tot;
struct ST2{
ar<int, 2> tree[N<<2];
int p[N<<2];
void push(int x, int lx, int rx){
if(lx == rx) return;
tree[x<<1][0] += p[x], tree[x<<1|1][0] += p[x];
p[x<<1] += p[x], p[x<<1|1] += p[x];
p[x] = 0;
}
void sett(int i, int v, int lx = 0, int rx = N, int x = 1){
if(lx == rx) { tree[x] = {v, i}; return; }
int m = (lx + rx) >> 1;
push(x, lx, rx);
if(i <= m) sett(i, v, lx, m, x<<1);
else sett(i, v, m+1, rx, x<<1|1);
tree[x] = min(tree[x<<1], tree[x<<1|1]);
}
void add(int l, int r, int v, int lx = 0, int rx = N, int x = 1){
if(lx > r || rx < l) return;
if(lx >= l && rx <= r){
tree[x][0] += v;
p[x] += v; return;
} int m = (lx + rx) >> 1;
push(x, lx, rx);
add(l, r, v, lx, m, x<<1),
add(l, r, v, m+1, rx, x<<1|1);
tree[x] = min(tree[x<<1], tree[x<<1|1]);
}
ar<int, 2> get(int l, int r, int lx = 0, int rx = N, int x = 1){
if(lx > r || rx < l) return {(int)1e18, (int)1e18};
if(lx >= l && rx <= r) return tree[x];
int m = (lx + rx) >> 1;
push(x, lx, rx);
return min(get(l, r, lx, m, x<<1), get(l, r, m+1, rx, x<<1|1));
}
}tree;
int res[N], pos[N];
vector<int> qq[N];
node a[N];
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
memset(cur.p[1], 128, sizeof cur.p[1]);
int n, m, q; cin>>n>>m>>q;
for(int i=0;i<q;i++){
cin>>a[i].t;
if(a[i].t == 1){
cin>>a[i].l>>a[i].r>>a[i].c>>a[i].k;
cur.add(a[i].l, a[i].r, a[i].k);
tot.add(a[i].l, a[i].r, a[i].k);
} if(a[i].t == 2){
cin>>a[i].l>>a[i].r>>a[i].k;
cur.add(a[i].l, a[i].r, -a[i].k);
cur.umax(a[i].l, a[i].r, 0);
} if(a[i].t == 3){
cin>>a[i].a>>a[i].b;
int c = cur.get(a[i].a), t = tot.get(a[i].a) - c;
if(a[i].b > c) res[i] = 0;
else {
qq[a[i].a].push_back(i);
pos[i] = t + a[i].b;
}
}
}
for(int i=1;i<=n;i++){
sort(qq[i].begin(), qq[i].end(), [&](int i, int j){
return (pos[i] > pos[j]);
});
if(qq[i].empty()) tree.sett(i, 1e18);
else tree.sett(i, pos[qq[i].back()]);
}
for(auto x : a){
if(x.t != 1) continue;
tree.add(x.l, x.r, -x.k);
auto mn = tree.get(x.l, x.r);
while(mn[0] <= 0){
int i = mn[1];
res[qq[i].back()] = x.c;
qq[i].pop_back();
if(qq[i].empty()) tree.sett(i, 1e18);
else tree.sett(i, pos[qq[i].back()]);
mn = tree.get(x.l, x.r);
}
}
for(int i=0;i<q;i++){
if(a[i].t == 3) cout<<res[i]<<"\n";
} cout<<"\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
14736 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
14736 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
141 ms |
27644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
885 ms |
61944 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
14736 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
169 ms |
27260 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
14736 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
14736 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
