#include<bits/stdc++.h>
using namespace std;
#define INT __int128
#define int int64_t
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define ll __int128
const int INF = 1e17;
const int MAXN = 250'009;
namespace special {
const int MAXN = 500001; // 1-based
int N = 400000;
ll A[MAXN];
struct Node {
ll sum; // Sum tag
ll min1; // Min value
ll min2; // Second Min value
ll minc; // Min value count
ll lazy; // Lazy tag
} T[MAXN * 4];
void merge(int t) {
// sum
T[t].sum = T[t << 1].sum + T[t << 1 | 1].sum;
if (T[t << 1].min1 == T[t << 1 | 1].min1) {
T[t].min1 = T[t << 1].min1;
T[t].min2 = min(T[t << 1].min2, T[t << 1 | 1].min2);
T[t].minc = T[t << 1].minc + T[t << 1 | 1].minc;
} else {
if (T[t << 1].min1 < T[t << 1 | 1].min1) {
T[t].min1 = T[t << 1].min1;
T[t].min2 = min(T[t << 1].min2, T[t << 1 | 1].min1);
T[t].minc = T[t << 1].minc;
} else {
T[t].min1 = T[t << 1 | 1].min1;
T[t].min2 = min(T[t << 1].min1, T[t << 1 | 1].min2);
T[t].minc = T[t << 1 | 1].minc;
}
}
}
void push_add(int t, int tl, int tr, ll v) {
if (v == 0) { return; }
T[t].sum += (tr - tl + 1) * v;
T[t].min1 += v;
if (T[t].min2 != INF) { T[t].min2 += v; }
T[t].lazy += v;
}
// corresponds to a chmax update
void push_min(int t, ll v, bool l) {
if (v <= T[t].min1) { return; }
T[t].sum -= T[t].min1 * T[t].minc;
T[t].min1 = v;
T[t].sum += T[t].min1 * T[t].minc;
}
void pushdown(int t, int tl, int tr) {
if (tl == tr) return;
// sum
int tm = (tl + tr) >> 1;
push_add(t << 1, tl, tm, T[t].lazy);
push_add(t << 1 | 1, tm + 1, tr, T[t].lazy);
T[t].lazy = 0;
// min
push_min(t << 1, T[t].min1, tl == tm);
push_min(t << 1 | 1, T[t].min1, tm + 1 == tr);
}
void build(int t = 1, int tl = 0, int tr = N - 1) {
T[t].lazy = 0;
if (tl == tr) {
T[t].sum = T[t].min1 = A[tl];
T[t].min2 = INF;
return;
}
int tm = (tl + tr) >> 1;
build(t << 1, tl, tm);
build(t << 1 | 1, tm + 1, tr);
merge(t);
}
void update_add(int l, int r, ll v, int t = 1, int tl = 0, int tr = N - 1) {
// cerr << "change!!!\n";
if (r < tl || tr < l) { return; }
if (l <= tl && tr <= r) {
push_add(t, tl, tr, v);
return;
}
pushdown(t, tl, tr);
int tm = (tl + tr) >> 1;
update_add(l, r, v, t << 1, tl, tm);
update_add(l, r, v, t << 1 | 1, tm + 1, tr);
merge(t);
}
void update_chmax(int l, int r, ll v, int t = 1, int tl = 0, int tr = N - 1) {
if (r < tl || tr < l || v <= T[t].min1) { return; }
if (l <= tl && tr <= r && v < T[t].min2) {
push_min(t, v, tl == tr);
return;
}
pushdown(t, tl, tr);
int tm = (tl + tr) >> 1;
update_chmax(l, r, v, t << 1, tl, tm);
update_chmax(l, r, v, t << 1 | 1, tm + 1, tr);
merge(t);
}
ll query_sum(int l, int r, int t = 1, int tl = 0, int tr = N - 1) {
if (r < tl || tr < l) { return 0; }
if (l <= tl && tr <= r) { return T[t].sum; }
pushdown(t, tl, tr);
int tm = (tl + tr) >> 1;
return query_sum(l, r, t << 1, tl, tm) +
query_sum(l, r, t << 1 | 1, tm + 1, tr);
}
}
struct SegTree {
const static int T = 1<<20;
int t[2*T];
void update(int l, int r, int val) {
l+=T, r+=T;
t[l]+=val;
if(l!=r) {
t[r]+=val;
}
while(l/2!=r/2) {
if(l%2==0) {
t[l+1]+=val;
}
if(r%2==1) {
t[r-1]+=val;
}
l/=2;
r/=2;
}
}
int query(int x) {
x+=T;
int ret = 0;
while(x){
ret += t[x];
x/=2;
}
return ret;
}
} seg;
struct SegTree2 {
const static int T = 1<<18;
pii t[2*T];
int lz[2*T];
SegTree2() {
for(int i=T;i<2*T;i++) {
t[i] = {INF, i-T};
}
for(int i=T-1;i;i--) {
t[i] = min(t[2*i], t[2*i+1]);
}
}
void push(int v) {
int l = 2*v, r = 2*v+1;
t[l].st += lz[v];
t[r].st += lz[v];
lz[l] += lz[v];
lz[r] += lz[v];
lz[v] = 0;
}
void update(int l, int r, int val, int tl=0, int tr=T-1, int v=1) {
if(l>r) return;
if(l==tl&&r==tr) {
t[v].st += val;
lz[v] += val;
return;
}
push(v);
int tm = (tl+tr)/2;
update(l, min(r, tm), val, tl, tm, 2*v);
update(max(tm+1, l), r, val, tm+1, tr, 2*v+1);
t[v] = min(t[2*v], t[2*v+1]);
}
pii query(int l, int r, int tl=0, int tr=T-1, int v=1) {
if(l>r) return make_pair(INF, -1);
if(l==tl&&r==tr) {
return t[v];
}
push(v);
int tm = (tl+tr)/2;
return min(query(l, min(r, tm), tl, tm, 2*v),
query(max(tm+1, l), r, tm+1, tr, 2*v+1));
}
} seg2;
vector<tuple<int, int, int, int>> Q;
int tab[MAXN];
int lim[MAXN];
pii info[MAXN];
int ans[MAXN];
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
vector<pii> zap;
int n, m, q;
cin >> n >> m >> q;
int cnt = 0;
int cnt3 = 0;
special::build();
for(int i=0;i<q;i++) {
int type;
cin >> type;
if(type==1) {
int l, r, c, k;
cin >> l >> r >> k >> c;
tab[cnt] = k;
Q.pb({l, r, c, k});
cnt++;
seg.update(l, r, c);
special::update_add(l, r, c);
}
if(type==2) {
int l, r, c;
cin >> l >> r >> c;
special::update_add(l, r, -c);
special::update_chmax(l, r, 0);
}
if(type==3) {
int a, b;
cin >> a >> b;
int diff = seg.query(a)-special::query_sum(a, a);
b += diff;
info[cnt3] = {cnt, b};
zap.pb({a, cnt3++});
}
}
sort(all(zap));
for(int i=0;i<cnt3;i++) {
int num = zap[i].nd;
seg2.update(i, i, -INF+info[num].nd);
pii X = seg2.query(i, i);
}
for(int i=0;i<cnt;i++) {
auto [l, r, C, k] = Q[i];
int s = -1;
int e = cnt3;
while(e-s>1) {
int m = (e+s)/2;
if(zap[m].st>=l) e = m;
else s = m;
}
int S = e;
s = -1, e = cnt3;
while(e-s>1) {
int m = (e+s)/2;
if(zap[m].st<=r) s = m;
else e = m;
}
int E = s;
seg2.update(S, E, -C);
while(true) {
pii x = seg2.query(0, cnt3-1);
if(x.st>0) break;
if(i<info[zap[x.nd].nd].st) ans[zap[x.nd].nd] = tab[i];
seg2.update(x.nd, x.nd, INF);
}
}
for(int i=0;i<cnt3;i++) {
cout << ans[i] << "\n";
}
}
Compilation message
foodcourt.cpp: In function 'int32_t main()':
foodcourt.cpp:262:7: warning: variable 'X' set but not used [-Wunused-but-set-variable]
262 | pii X = seg2.query(i, i);
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
44 ms |
94284 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
44 ms |
94284 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
151 ms |
97464 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
690 ms |
107744 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
44 ms |
94284 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
138 ms |
98140 KB |
Output is correct |
| 2 |
Correct |
174 ms |
99256 KB |
Output is correct |
| 3 |
Correct |
153 ms |
98692 KB |
Output is correct |
| 4 |
Correct |
154 ms |
97456 KB |
Output is correct |
| 5 |
Correct |
208 ms |
105916 KB |
Output is correct |
| 6 |
Correct |
151 ms |
106140 KB |
Output is correct |
| 7 |
Correct |
110 ms |
106684 KB |
Output is correct |
| 8 |
Correct |
83 ms |
104744 KB |
Output is correct |
| 9 |
Correct |
115 ms |
113268 KB |
Output is correct |
| 10 |
Correct |
96 ms |
113092 KB |
Output is correct |
| 11 |
Correct |
131 ms |
111072 KB |
Output is correct |
| 12 |
Correct |
146 ms |
113528 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
44 ms |
94284 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
44 ms |
94284 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
