#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
const ll INF = 1e18;
const int N = 3e5+10;
// value in point queries
// max(a_i+x, b) for (x, b) on [L, R] updates
struct maxtree {
vector<ll> t;
vector<pii> lz;
void init(int k) {
int sz=1;
while (sz < 4*k) sz*=2;
t.resize(sz), lz.resize(sz);
}
void push(int v) {
lz[2*v] = {
lz[v].first+lz[2*v].first,
max(lz[v].first+lz[2*v].second, lz[v].second)
}, t[2*v]=max(t[2*v]+lz[v].first, lz[v].second);
lz[2*v+1] = {
lz[v].first+lz[2*v+1].first,
max(lz[v].first+lz[2*v+1].second, lz[v].second)
}, t[2*v+1]=max(t[2*v+1]+lz[v].first, lz[v].second);
lz[v]={0, 0};
}
void upd(int v, int l, int r, int ql, int qr, ll val) {
if (l > qr || r < ql) return;
if (l >= ql && r <= qr) {
lz[v].first+=val;
if (l == r) t[v]=max(t[v]+val, 0ll);
if (l < r) push(v);
return;
} int m=(l+r)/2; push(v);
upd(2*v, l, m, ql, qr, val), upd(2*v+1, m+1, r, ql, qr, val);
}
ll que(int v, int l, int r, int p) {
if (l == r) return t[v];
ll m=(l+r)/2; push(v);
if (p <= m) return que(2*v, l, m, p);
return que(2*v+1, m+1, r, p);
}
};
ll tp[N], l[N], r[N], c[N], k[N], lft[N], x[N], ans[N];
struct segtree {
vector<pii> t;
void init(int sz) {
int k=1;
while (k < 4*sz) k*=2;
t.resize(k);
}
pii mrg(pii l, pii r) {
return make_pair(l.first+r.first, l.second+r.second);
}
void upd(int v, int l, int r, int p, pii val) {
if (l == r) {
t[v]=val;
return;
} int m=(l+r)/2;
if (p <= m) upd(2*v, l, m, p, val);
else upd(2*v+1, m+1, r, p, val);
t[v]=mrg(t[2*v], t[2*v+1]);
}
int que(int v, int l, int r, ll x) {
if (l == r) return t[v].second;
int m=(l+r)/2;
if (t[2*v].first >= x) return que(2*v, l, m, x);
return que(2*v+1, m+1, r, x-t[2*v].first);
}
};
vector<int> add[N], rem[N];
vector<int> qx[N];
int main() {
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
int n, m, q; cin>>n>>m>>q;
maxtree mx, mx2; mx.init(n+10), mx2.init(n+10);
segtree t; t.init(q+10);
for (int i=1; i<=q; ++i) {
cin>>tp[i];
if (tp[i] == 1) {
cin>>l[i]>>r[i]>>c[i]>>k[i];
mx.upd(1, 1, n, l[i], r[i], k[i]);
mx2.upd(1, 1, n, l[i], r[i], k[i]);
add[l[i]].push_back(i);
rem[r[i]+1].push_back(i);
} else if (tp[i] == 2) {
cin>>l[i]>>r[i]>>k[i];
mx.upd(1, 1, n, l[i], r[i], -k[i]);
} else {
cin>>l[i]>>r[i];
lft[i]=mx.que(1, 1, n, l[i]);
x[i]=r[i]+(mx2.que(1, 1, n, l[i])-lft[i]);
if (lft[i] < r[i]) ans[i]=-1;
qx[l[i]].push_back(i);
}
}
for (int i=1; i<=n; ++i) {
for (auto j : add[i]) t.upd(1, 1, q, j, {k[j], c[j]});
for (auto j : rem[i]) t.upd(1, 1, q, j, {0, 0});
for (auto j : qx[i]) {
if (ans[j] == -1) continue;
ans[j]=t.que(1, 1, q, x[j]);
}
}
for (int i=1; i<=q; ++i) {
if (tp[i] != 3) continue;
if (ans[i] == -1) cout<<0<<"\n";
else cout<<ans[i]<<"\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
37980 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
37980 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
92 ms |
58964 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
486 ms |
113492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
37980 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
115 ms |
59368 KB |
Output is correct |
| 2 |
Correct |
118 ms |
59988 KB |
Output is correct |
| 3 |
Correct |
127 ms |
59980 KB |
Output is correct |
| 4 |
Correct |
82 ms |
58916 KB |
Output is correct |
| 5 |
Correct |
121 ms |
59268 KB |
Output is correct |
| 6 |
Correct |
136 ms |
48708 KB |
Output is correct |
| 7 |
Correct |
30 ms |
45500 KB |
Output is correct |
| 8 |
Correct |
30 ms |
33564 KB |
Output is correct |
| 9 |
Correct |
66 ms |
58700 KB |
Output is correct |
| 10 |
Correct |
79 ms |
44152 KB |
Output is correct |
| 11 |
Correct |
93 ms |
58836 KB |
Output is correct |
| 12 |
Correct |
94 ms |
58960 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
37980 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
37980 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
