#include "bits/stdc++.h"
using namespace std;
#define int long long
struct segtree_basic {
struct node {
int lazyval, mi, ma, sum; char lazytag;
int len; // not changing
};
int stok;
vector<node> st;
void bu(int l, int r, int idx) {
st[idx].lazyval = st[idx].mi = st[idx].ma = st[idx].sum = 0;
st[idx].lazytag = '?';
st[idx].len = r - l + 1;
if(l == r) {
return;
}
int mid = (l + r) >> 1;
bu(l, mid, 2*idx+1);
bu(mid+1, r, 2*idx+2);
}
void push_down(int idx) {
if(st[idx].lazytag == '?') return;
if(st[idx].lazytag == ':') {
st[2*idx+1].lazyval = st[idx].lazyval;
st[2*idx+1].mi = st[idx].lazyval;
st[2*idx+1].ma = st[idx].lazyval;
st[2*idx+1].sum = st[idx].lazyval * st[2*idx+1].len;
st[2*idx+1].lazytag = ':';
st[2*idx+2].lazyval = st[idx].lazyval;
st[2*idx+2].mi = st[idx].lazyval;
st[2*idx+2].ma = st[idx].lazyval;
st[2*idx+2].sum = st[idx].lazyval * st[2*idx+2].len;
st[2*idx+2].lazytag = ':';
}
else {
st[2*idx+1].lazyval += st[idx].lazyval;
st[2*idx+1].mi += st[idx].lazyval;
st[2*idx+1].ma += st[idx].lazyval;
st[2*idx+1].sum += st[idx].lazyval * st[2*idx+1].len;
st[2*idx+1].lazytag = (st[2*idx+1].lazytag == ':' ? ':' : '+');
st[2*idx+2].lazyval += st[idx].lazyval;
st[2*idx+2].mi += st[idx].lazyval;
st[2*idx+2].ma += st[idx].lazyval;
st[2*idx+2].sum += st[idx].lazyval * st[2*idx+2].len;
st[2*idx+2].lazytag = (st[2*idx+2].lazytag == ':' ? ':' : '+');
}
st[idx].lazytag = '?';
st[idx].lazyval = 0;
}
void push_up(int idx) {
st[idx].mi = min(st[2*idx+1].mi, st[2*idx+2].mi);
st[idx].ma = max(st[2*idx+1].ma, st[2*idx+2].ma);
st[idx].sum = st[2*idx+1].sum + st[2*idx+2].sum;
}
void u1(int l, int r, int constl, int constr, int idx, int val) { // range := v
if(l <= constl && constr <= r) {
st[idx].lazyval = val;
st[idx].mi = val;
st[idx].ma = val;
st[idx].sum = val * st[idx].len;
st[idx].lazytag = ':';
return;
}
int mid = (constl + constr) >> 1;
push_down(idx);
if(mid < l || r < constl) u1(l, r, mid+1, constr, 2*idx+2, val);
else if(constr < l || r < mid + 1) u1(l, r, constl, mid, 2*idx+1, val);
else {
u1(l, r, constl, mid, 2*idx+1, val);
u1(l, r, mid+1, constr, 2*idx+2, val);
}
push_up(idx);
}
void u2(int l, int r, int constl, int constr, int idx, int val) { // range += v
if(l <= constl && constr <= r) {
st[idx].lazyval += val;
st[idx].mi += val;
st[idx].ma += val;
st[idx].sum += val * st[idx].len;
st[idx].lazytag = (st[idx].lazytag == ':' ? ':' : '+');
return;
}
int mid = (constl + constr) >> 1;
push_down(idx);
if(mid < l || r < constl) u2(l, r, mid+1, constr, 2*idx+2, val);
else if(constr < l || r < mid + 1) u2(l, r, constl, mid, 2*idx+1, val);
else {
u2(l, r, constl, mid, 2*idx+1, val);
u2(l, r, mid+1, constr, 2*idx+2, val);
}
push_up(idx);
}
int qu1(int l, int r, int constl, int constr, int idx) { // range min
if(l <= constl && constr <= r) return st[idx].mi;
int mid = (constl + constr) >> 1;
push_down(idx);
if(mid < l || r < constl) return qu1(l, r, mid+1, constr, 2*idx+2);
else if(constr < l || r < mid + 1) return qu1(l, r, constl, mid, 2*idx+1);
else {
return min(qu1(l, r, constl, mid, 2*idx+1), qu1(l, r, mid+1, constr, 2*idx+2));
}
}
int qu2(int l, int r, int constl, int constr, int idx) { // range max
if(l <= constl && constr <= r) return st[idx].ma;
int mid = (constl + constr) >> 1;
push_down(idx);
if(mid < l || r < constl) return qu2(l, r, mid+1, constr, 2*idx+2);
else if(constr < l || r < mid + 1) return qu2(l, r, constl, mid, 2*idx+1);
else {
return max(qu2(l, r, constl, mid, 2*idx+1), qu2(l, r, mid+1, constr, 2*idx+2));
}
}
int qu3(int l, int r, int constl, int constr, int idx) { // range sum
if(l <= constl && constr <= r) return st[idx].sum;
int mid = (constl + constr) >> 1;
push_down(idx);
if(mid < l || r < constl) return qu3(l, r, mid+1, constr, 2*idx+2);
else if(constr < l || r < mid + 1) return qu3(l, r, constl, mid, 2*idx+1);
else {
return qu3(l, r, constl, mid, 2*idx+1) + qu3(l, r, mid+1, constr, 2*idx+2);
}
}
int qu4(int l, int r, int constl, int constr, int idx, int val) { // first at least v
if(l <= constl && constr <= r) {
if(st[idx].ma < val) return -1;
while(constl < constr) {
int mid = (constl + constr) >> 1;
push_down(idx);
if(st[2*idx+1].ma >= val) constr = mid, idx = 2*idx + 1;
else constl = mid+1, idx = 2*idx + 2;
}
return constl;
}
int mid = (constl + constr) >> 1;
push_down(idx);
if(mid < l || r < constl) return qu4(l, r, mid+1, constr, 2*idx+2, val);
else if(constr < l || r < mid + 1) return qu4(l, r, constl, mid, 2*idx+1, val);
else {
int lchild = qu4(l, r, constl, mid, 2*idx+1, val);
if(lchild != -1) return lchild;
return qu4(l, r, mid+1, constr, 2*idx+2, val);
}
}
int qu5(int l, int r, int constl, int constr, int idx, int val) { // first at most v
if(l <= constl && constr <= r) {
if(st[idx].mi > val) return -1;
while(constl < constr) {
int mid = (constl + constr) >> 1;
push_down(idx);
if(st[2*idx+1].mi <= val) constr = mid, idx = 2*idx + 1;
else constl = mid+1, idx = 2*idx + 2;
}
return constl;
}
int mid = (constl + constr) >> 1;
push_down(idx);
if(mid < l || r < constl) return qu5(l, r, mid+1, constr, 2*idx+2, val);
else if(constr < l || r < mid + 1) return qu5(l, r, constl, mid, 2*idx+1, val);
else {
int lchild = qu5(l, r, constl, mid, 2*idx+1, val);
if(lchild != -1) return lchild;
return qu5(l, r, mid+1, constr, 2*idx+2, val);
}
}
int qu6(int l, int r, int constl, int constr, int idx, int val) { // last at least v
if(l <= constl && constr <= r) {
if(st[idx].ma < val) return -1;
while(constl < constr) {
int mid = (constl + constr) >> 1;
push_down(idx);
if(st[2*idx+2].ma >= val) constl = mid+1, idx = 2*idx + 2;
else constr = mid, idx = 2*idx + 1;
}
return constl;
}
int mid = (constl + constr) >> 1;
push_down(idx);
if(mid < l || r < constl) return qu6(l, r, mid+1, constr, 2*idx+2, val);
else if(constr < l || r < mid + 1) return qu6(l, r, constl, mid, 2*idx+1, val);
else {
int rchild = qu6(l, r, mid+1, constr, 2*idx+2, val);
if(rchild != -1) return rchild;
return qu6(l, r, constl, mid, 2*idx+1, val);
}
}
int qu7(int l, int r, int constl, int constr, int idx, int val) { // last at most v
if(l <= constl && constr <= r) {
if(st[idx].mi > val) return -1;
while(constl < constr) {
int mid = (constl + constr) >> 1;
push_down(idx);
if(st[2*idx+2].mi <= val) constl = mid+1, idx = 2*idx + 2;
else constr = mid, idx = 2*idx + 1;
}
return constl;
}
int mid = (constl + constr) >> 1;
push_down(idx);
if(mid < l || r < constl) return qu7(l, r, mid+1, constr, 2*idx+2, val);
else if(constr < l || r < mid + 1) return qu7(l, r, constl, mid, 2*idx+1, val);
else {
int rchild = qu7(l, r, mid+1, constr, 2*idx+2, val);
if(rchild != -1) return rchild;
return qu7(l, r, constl, mid, 2*idx+1, val);
}
}
int qu8(int l, int r, int constl, int constr, int idx, int val) { // first partial sum at least v, only works when partial sum is non-decreasing
if(l <= constl && constr <= r) {
if(st[idx].sum < val) return -1;
while(constl < constr) {
int mid = (constl + constr) >> 1;
push_down(idx);
if(st[2*idx+1].sum >= val) {
idx = 2*idx+1, constr = mid;
}
else {
val -= st[2*idx+1].sum;
idx = 2*idx+2, constl = mid+1;
}
}
return constl;
}
int mid = (constl + constr) >> 1;
push_down(idx);
if(mid < l || r < constl) return qu8(l, r, mid+1, constr, 2*idx+2, val - st[2*idx+1].sum);
else if(constr < l || r < mid+1) return qu8(l, r, constl, mid, 2*idx+1, val);
else {
int lchild = qu8(l, r, constl, mid, 2*idx+1, val);
if(lchild != -1) return lchild;
return qu8(l, r, mid+1, constr, 2*idx+2, val - st[2*idx+1].sum);
}
}
public:
void resize(int k) {
st.resize(4*k + 10);
stok = k;
bu(0, k, 0);
}
void range_assign(int l, int r, int v) { u1(l, r, 0, stok, 0, v); }
void range_add(int l, int r, int v) { u2(l, r, 0, stok, 0, v); }
int query_min(int l, int r) { return qu1(l, r, 0, stok, 0); }
int query_max(int l, int r) { return qu2(l, r, 0, stok, 0); }
int query_sum(int l, int r) { return qu3(l, r, 0, stok, 0); }
int query_firstAtLeast(int l, int r, int v) { return qu4(l, r, 0, stok, 0, v); }
int query_firstAtMost(int l, int r, int v) { return qu5(l, r, 0, stok, 0, v); }
int query_lastAtLeast(int l, int r, int v) { return qu6(l, r, 0, stok, 0, v); }
int query_lastAtMost(int l, int r, int v) { return qu7(l, r, 0, stok, 0, v); }
int query_firstPSAtLeast(int l, int r, int v) { return qu8(l, r, 0, stok, 0, v); }
};
struct segtree_bruh {
struct node {
int mss = 0, sum = 0, id;
};
vector<node> st;
int stok;
void push_up(int idx) {
st[idx].sum = st[2*idx+1].sum + st[2*idx+2].sum;
st[idx].mss = max(st[2*idx+2].mss, st[2*idx+1].mss + st[2*idx+2].sum);
if(st[2*idx+2].mss < st[2*idx+1].mss + st[2*idx+2].sum) st[idx].id = st[2*idx+1].id;
else st[idx].id = st[2*idx+2].id;
}
void init(int l, int r, int idx) {
if(l == r) {
st[idx].id = l;
return;
}
int m = (l + r) >> 1;
init(l, m, (idx << 1) + 1);
init(m + 1, r, (idx << 1) + 2);
push_up(idx);
}
void u(int l, int r, int tar, int idx, int val) {
if(l == r) {
st[idx].sum = val;
st[idx].mss = max(val, 0ll);
return;
}
int mid = (l + r) >> 1;
if(tar <= mid) u(l, mid, tar, 2*idx+1, val);
else u(mid+1, r, tar, 2*idx+2, val);
push_up(idx);
}
pair<pair<int, int>, int> qu(int l, int r, int constl, int constr, int idx) {
if(l <= constl && constr <= r) return {{st[idx].mss, st[idx].id}, st[idx].sum};
int mid = (constl + constr) >> 1;
if(mid < l || r < constl) return qu(l, r, mid+1, constr, 2*idx+2);
else if(constr < l || r < mid+1) return qu(l, r, constl, mid, 2*idx+1);
else {
pair<pair<int, int>, int> lc = qu(l, r, constl, mid, 2*idx+1);
pair<pair<int, int>, int> rc = qu(l, r, mid+1, constr, 2*idx+2);
if(rc.first.first >= lc.first.first + rc.second) return rc;
else return {{lc.first.first + rc.second, lc.first.second}, lc.second + rc.second};
}
}
void resize(int k) {
stok = k;
st.resize(4*k + 10);
init(0, k, 0);
}
void point_add(int i, int v) {
u(0, stok, i, 0, v);
}
pair<int, int> prefix_mss(int i) {
return qu(1, i, 0, stok, 0).first;
}
};
const int MAXN = 250050;
int bit[MAXN];
void not_add(int x, int v) {
for(;x<MAXN;x+=x&-x) bit[x] += v;
}
int sum(int x) {
int s=0;
for(;x;x-=x&-x) s += bit[x];
return s;
}
int32_t main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, m, q;
cin >> n >> m >> q;
int l[q+1], r[q+1], c[q+1], k[q+1], a[q+1], b[q+1], ans[q+1], tyy[q+1];
set<int> add[n+1], sub[n+2], qry[n+1];
for(int i=1; i<=q; i++) {
int ty;
cin >> ty;
tyy[i] = ty;
if(ty == 1) {
cin >> l[i] >> r[i] >> c[i] >> k[i];
add[l[i]].insert(i);
sub[r[i]+1].insert(i);
}
else if(ty == 2) {
cin >> l[i] >> r[i] >> k[i];
k[i] = -k[i];
c[i] = 0;
add[l[i]].insert(i);
sub[r[i]+1].insert(i);
}
else {
cin >> a[i] >> b[i];
k[i] = 0;
qry[a[i]].insert(i);
}
}
segtree_basic stb;
segtree_bruh str;
stb.resize(q);
str.resize(q);
for(int i=1; i<=n; i++) {
for(int x: add[i]) {
str.point_add(x, k[x]);
if(k[x] < 0) not_add(x, k[x]);
else stb.range_add(x, x, k[x]);
}
for(int x: sub[i]) {
str.point_add(x, -k[x]);
if(k[x] < 0) not_add(x, -k[x]);
else stb.range_add(x, x, -k[x]);
}
for(int x: qry[i]) {
pair<int, int> bruh = str.prefix_mss(x);
/*
cout << "x = " << x << ":\n";
cout << -sum(x) << ' ' << b[x] << '\n';
cout << bruh.first << ' ' << bruh.second << '\n';
cout << stb.query_sum(bruh.second, x) << '\n';
*/
int fin = bruh.first + sum(x) - sum(bruh.second);
// cout << fin << '\n';
if(fin < b[x]) {
ans[x] = 0; continue;
}
fin = stb.query_firstPSAtLeast(bruh.second, x, -sum(x) +sum(bruh.second) + b[x]);
// cout << "ans["<<x<<"] = "<<fin << "\n";
ans[x] = c[fin];
}
}
for(int i=1; i<=q; i++) if(tyy[i] == 3) cout << ans[i] << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
1236 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
1236 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
114 ms |
38664 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
535 ms |
136260 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
1236 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
118 ms |
34636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
1236 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
1236 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
