#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 3e5 + 10;
const int MOD = 1e9 + 7;
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
int u = uniform_int_distribution<int>(x, y)(rng);
return u;
}
int bm(int b, int p) { // bigmod
if(p==0) return 1;
int r = bm(b, p/2);
if(p&1) return (((r*r) % MOD) * b) % MOD;
return (r*r) % MOD;
}
int N, M, Q;
struct segtree_beats {
bool cmp(__int128 x, __int128 y) { return x > y; }
int stok;
const __int128 extr = 2e18;
struct node {
__int128 max1, max2, maxc;
__int128 min1, min2, minc;
__int128 lazy, sum;
__int128 l, r;
};
vector<node> a;
void pushtag_max(int idx, __int128 val) {
if(val >= a[idx].max1) return;
a[idx].sum -= (a[idx].max1 - val) * a[idx].maxc;
a[idx].max1 = val;
if(a[idx].l == a[idx].r) {
a[idx].min1 = val;
}
else {
if(a[idx].min1 >= val) {
a[idx].min1 = val;
a[idx].min2 = extr;
a[idx].minc = a[idx].r - a[idx].l + 1;
}
else if(a[idx].min2 > val && a[idx].min2 != extr) {
a[idx].min2 = val;
}
}
}
void pushtag_min(int idx, __int128 val) {
if(val <= a[idx].min1) return;
a[idx].sum += (val - a[idx].min1) * a[idx].minc;
a[idx].min1 = val;
if(a[idx].l == a[idx].r) {
a[idx].max1 = val;
}
else {
if(a[idx].max1 <= val) {
a[idx].max1 = val;
a[idx].max2 = -extr;
a[idx].maxc = a[idx].r - a[idx].l + 1;
}
else if(a[idx].max2 < val && a[idx].max2 != -extr) {
a[idx].max2 = val;
}
}
}
void pushtag_add(int idx, __int128 val) {
a[idx].max1 += val;
if(a[idx].max2 != -extr) a[idx].max2 += val;
a[idx].min1 += val;
if(a[idx].min2 != extr) a[idx].min2 += val;
a[idx].lazy += val;
a[idx].sum += val * (a[idx].r - a[idx].l + 1);
}
void pushdown(int idx) {
pushtag_add(2*idx+1, a[idx].lazy);
pushtag_add(2*idx+2, a[idx].lazy);
a[idx].lazy = 0;
pushtag_max(2*idx+1, a[idx].max1);
pushtag_max(2*idx+2, a[idx].max1);
pushtag_min(2*idx+1, a[idx].min1);
pushtag_min(2*idx+2, a[idx].min1);
}
void pushup(int idx) {
__int128 max1, max2, maxc;
__int128 min1, min2, minc;
__int128 lazy, sum;
__int128 l, r;
a[idx].max1 = max(a[2*idx+1].max1, a[2*idx+2].max1);
a[idx].max2 = (a[2*idx+1].max1 == a[2*idx+2].max1 ?
max(a[2*idx+1].max2, a[2*idx+2].max2) :
(a[2*idx+1].max1 < a[2*idx+2].max1 ?
max(a[2*idx+1].max1, a[2*idx+2].max2) :
max(a[2*idx+1].max2, a[2*idx+2].max1)
));
a[idx].maxc = (a[2*idx+1].max1 == a[2*idx+2].max1 ?
a[2*idx+1].maxc + a[2*idx+2].maxc :
(a[2*idx+1].max1 < a[2*idx+2].max1 ?
a[2*idx+2].maxc :
a[2*idx+1].maxc)
);
a[idx].min1 = min(a[2*idx+1].min1, a[2*idx+2].min1);
a[idx].min2 = (a[2*idx+1].min1 == a[2*idx+2].min1 ?
min(a[2*idx+1].min2, a[2*idx+2].min2) :
(a[2*idx+1].min1 > a[2*idx+2].min1 ?
min(a[2*idx+1].min1, a[2*idx+2].min2) :
min(a[2*idx+1].min2, a[2*idx+2].min1)
));
a[idx].minc = (a[2*idx+1].min1 == a[2*idx+2].min1 ?
a[2*idx+1].minc + a[2*idx+2].minc :
(a[2*idx+1].min1 > a[2*idx+2].min1 ?
a[2*idx+2].minc :
a[2*idx+1].minc)
);
a[idx].sum = a[2*idx+1].sum + a[2*idx+2].sum;
}
void init1(int l, int r, int idx, __int128 val) {
a[idx].l = l, a[idx].r = r;
if(l == r) {
a[idx].max1 = a[idx].min1 = val;
a[idx].max2 = -extr;
a[idx].min2 = extr;
a[idx].maxc = a[idx].minc = 1;
a[idx].lazy = 0;
a[idx].sum = val;
return;
}
int mid = (l+r) >> 1;
init1(l, mid, 2*idx+1, val);
init1(mid+1, r, 2*idx+2, val);
pushup(idx);
}
void u1(int l, int r, int constl, int constr, int idx, __int128 v) {
if(v >= a[idx].max1) return;
if(l<=constl && constr<=r && v>a[idx].max2) {
pushtag_max(idx, v);
return;
}
pushdown(idx);
int mid = (constl+constr) >> 1;
if(mid < l || r < constl) u1(l, r, mid+1, constr, 2*idx+2, v);
else if(constr < l || r < mid+1) u1(l, r, constl, mid, 2*idx+1, v);
else {
u1(l, r, constl, mid, 2*idx+1, v);
u1(l, r, mid+1, constr, 2*idx+2, v);
}
pushup(idx);
}
void u2(int l, int r, int constl, int constr, int idx, __int128 v) {
if(v <= a[idx].min1) return;
if(l<=constl && constr<=r && v<a[idx].min2) {
pushtag_min(idx, v);
return;
}
pushdown(idx);
int mid = (constl+constr) >> 1;
if(mid < l || r < constl) u2(l, r, mid+1, constr, 2*idx+2, v);
else if(constr < l || r < mid+1) u2(l, r, constl, mid, 2*idx+1, v);
else {
u2(l, r, constl, mid, 2*idx+1, v);
u2(l, r, mid+1, constr, 2*idx+2, v);
}
pushup(idx);
}
void u3(int l, int r, int constl, int constr, int idx, __int128 v) {
if(l <= constl && constr <= r) {
pushtag_add(idx, v);
return;
}
pushdown(idx);
int mid = (constl+constr) >> 1;
if(mid < l || r < constl) u3(l, r, mid+1, constr, 2*idx+2, v);
else if(constr < l || r < mid+1) u3(l, r, constl, mid, 2*idx+1, v);
else {
u3(l, r, constl, mid, 2*idx+1, v);
u3(l, r, mid+1, constr, 2*idx+2, v);
}
pushup(idx);
}
__int128 qu(int l, int r, int constl, int constr, int idx) {
if(l <= constl && constr <= r) {
return a[idx].sum;
}
pushdown(idx);
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 {
return qu(l, r, constl, mid, 2*idx+1) + qu(l, r, mid+1, constr, 2*idx+2);
}
}
public:
void resize(int k) {
stok = k;
a.resize(4*k + 10);
}
void init(__int128 v) { // Initialize everything to v
init1(0, stok, 0, v);
}
void min_with(int l, int r, __int128 v) {
u1(l, r, 0, stok, 0, v);
}
void max_with(int l, int r, __int128 v) {
u2(l, r, 0, stok, 0, v);
}
void range_add(int l, int r, __int128 v) {
u3(l, r, 0, stok, 0, v);
}
long long query_sum(int l, int r) {
return (long long)qu(l, r, 0, stok, 0);
}
};
segtree_beats a;
void join(int l, int r, int c, int k) {
a.range_add(l, r, k);
}
void leave(int l, int r, int k) {
a.range_add(l, r, -k);
a.max_with(l, r, 0);
}
int service(int shop, int b) {
return (a.query_sum(shop, shop) >= b ? 1 : 0);
}
void solve(int tc) {
cin >> N >> M >> Q;
a.resize(N);
a.init(0);
while(Q--) {
int t;
cin >> t;
if(t == 1) {
int l, r, c, k;
cin >> l >> r >> c >> k;
join(l, r, c, k);
}
else if(t == 2) {
int l, r, k;
cin >> l >> r >> k;
leave(l, r, k);
}
else {
int a, b;
cin >> a >> b;
cout << service(a, b) << "\n";
}
}
}
int32_t main(){
ios::sync_with_stdio(0); cin.tie(0);
int t = 1; //cin >> t;
for(int i=1; i<=t; i++) {
solve(i);
}
}
Compilation message
foodcourt.cpp: In member function 'void segtree_beats::pushup(long long int)':
foodcourt.cpp:86:18: warning: unused variable 'max1' [-Wunused-variable]
86 | __int128 max1, max2, maxc;
| ^~~~
foodcourt.cpp:86:24: warning: unused variable 'max2' [-Wunused-variable]
86 | __int128 max1, max2, maxc;
| ^~~~
foodcourt.cpp:86:30: warning: unused variable 'maxc' [-Wunused-variable]
86 | __int128 max1, max2, maxc;
| ^~~~
foodcourt.cpp:87:18: warning: unused variable 'min1' [-Wunused-variable]
87 | __int128 min1, min2, minc;
| ^~~~
foodcourt.cpp:87:24: warning: unused variable 'min2' [-Wunused-variable]
87 | __int128 min1, min2, minc;
| ^~~~
foodcourt.cpp:87:30: warning: unused variable 'minc' [-Wunused-variable]
87 | __int128 min1, min2, minc;
| ^~~~
foodcourt.cpp:88:18: warning: unused variable 'lazy' [-Wunused-variable]
88 | __int128 lazy, sum;
| ^~~~
foodcourt.cpp:88:24: warning: unused variable 'sum' [-Wunused-variable]
88 | __int128 lazy, sum;
| ^~~
foodcourt.cpp:89:18: warning: unused variable 'l' [-Wunused-variable]
89 | __int128 l, r;
| ^
foodcourt.cpp:89:21: warning: unused variable 'r' [-Wunused-variable]
89 | __int128 l, r;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
1228 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
1228 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
168 ms |
41304 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
753 ms |
146276 KB |
Output is correct |
| 2 |
Correct |
655 ms |
126536 KB |
Output is correct |
| 3 |
Correct |
786 ms |
162884 KB |
Output is correct |
| 4 |
Correct |
547 ms |
160052 KB |
Output is correct |
| 5 |
Correct |
548 ms |
122244 KB |
Output is correct |
| 6 |
Correct |
781 ms |
163084 KB |
Output is correct |
| 7 |
Correct |
85 ms |
4616 KB |
Output is correct |
| 8 |
Correct |
82 ms |
4484 KB |
Output is correct |
| 9 |
Correct |
670 ms |
163072 KB |
Output is correct |
| 10 |
Correct |
663 ms |
163172 KB |
Output is correct |
| 11 |
Correct |
784 ms |
163180 KB |
Output is correct |
| 12 |
Correct |
738 ms |
163028 KB |
Output is correct |
| 13 |
Correct |
742 ms |
163012 KB |
Output is correct |
| 14 |
Correct |
818 ms |
163036 KB |
Output is correct |
| 15 |
Correct |
881 ms |
163028 KB |
Output is correct |
| 16 |
Correct |
877 ms |
162864 KB |
Output is correct |
| 17 |
Correct |
861 ms |
163028 KB |
Output is correct |
| 18 |
Correct |
801 ms |
163164 KB |
Output is correct |
| 19 |
Correct |
891 ms |
163148 KB |
Output is correct |
| 20 |
Correct |
825 ms |
163032 KB |
Output is correct |
| 21 |
Correct |
906 ms |
162928 KB |
Output is correct |
| 22 |
Correct |
853 ms |
163044 KB |
Output is correct |
| 23 |
Correct |
848 ms |
163024 KB |
Output is correct |
| 24 |
Correct |
865 ms |
163032 KB |
Output is correct |
| 25 |
Correct |
548 ms |
126748 KB |
Output is correct |
| 26 |
Correct |
541 ms |
162648 KB |
Output is correct |
| 27 |
Correct |
645 ms |
162680 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
1228 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
116 ms |
40900 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
1228 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
1228 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
