#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
const ll inf = 1e18;
struct segtree{
struct node{
ll sm, lazy_assign, lazy_add, mx, mn;
node(){
sm = 0LL, mx = 0LL, mn = 0LL, lazy_assign = -inf, lazy_add = 0LL;
}
void calc(node a, node b){
sm = a.sm+b.sm;
mx = max(a.mx, b.mx);
mn = min(a.mn, b.mn);
}
};
int k;
vector<node> v;
segtree(int n){
k = 1;
while(k <= n) k*=2; k*=2;
v.resize(k, node());
}
void chmx(int l, int r, int nd, int a, int b, ll x, ll ex, bool tt){
if(a > r || b < l || v[nd].mn >= x){
if(tt){
v[nd].lazy_assign = ex;
v[nd].lazy_add = 0LL;
v[nd].sm = (b-a+1)*ex;
v[nd].mn = ex;
v[nd].mx = ex;
}
else{
v[nd].lazy_add+=ex;
v[nd].sm+=(b-a+1)*ex;
v[nd].mn+=ex;
v[nd].mx+=ex;
}
return;
}
if(a >= l && b <= r && v[nd].mx <= x){
v[nd].lazy_assign = x;
v[nd].lazy_add = 0LL;
v[nd].sm = (b-a+1)*x;
v[nd].mn = x;
v[nd].mx = x;
return;
}
int md = (a+b)/2;
if(!tt){
ex+=v[nd].lazy_add;
if(v[nd].lazy_assign != -inf){
ex+=v[nd].lazy_assign;
tt = 1;
}
}
v[nd].lazy_add = 0LL;
v[nd].lazy_assign = -inf;
chmx(l, r, 2*nd, a, md, x, ex, tt);
chmx(l, r, 2*nd+1, md+1, b, x, ex, tt);
if(2*nd+1 < k) v[nd].calc(v[2*nd], v[2*nd+1]);
}
void chmx(int l, int r, ll x){
chmx(l, r, 1, 0, k/2-1, x, 0LL, 0);
}
void add(int l, int r, int nd, int a, int b, ll x, ll ex, bool tt){
if(a > r || b < l){
if(tt){
v[nd].lazy_assign = ex;
v[nd].lazy_add = 0LL;
v[nd].sm = (b-a+1)*ex;
v[nd].mn = ex;
v[nd].mx = ex;
}
else{
v[nd].lazy_add+=ex;
v[nd].sm+=(b-a+1)*ex;
v[nd].mn+=ex;
v[nd].mx+=ex;
}
return;
}
if(a >= l && b <= r){
if(tt){
v[nd].lazy_assign = ex;
v[nd].lazy_add = 0LL;
v[nd].sm = (b-a+1)*ex;
v[nd].mn = ex;
v[nd].mx = ex;
}
else{
v[nd].lazy_add+=ex;
v[nd].sm+=(b-a+1)*ex;
v[nd].mn+=ex;
v[nd].mx+=ex;
}
v[nd].lazy_add+=x;
v[nd].sm+=(b-a+1)*x;
v[nd].mn+=x;
v[nd].mx+=x;
return;
}
int md = (a+b)/2;
if(!tt){
ex+=v[nd].lazy_add;
if(v[nd].lazy_assign != -inf){
ex+=v[nd].lazy_assign;
tt = 1;
}
}
v[nd].lazy_add = 0LL;
v[nd].lazy_assign = -inf;
add(l, r, 2*nd, a, md, x, ex, tt);
add(l, r, 2*nd+1, md+1, b, x, ex, tt);
if(2*nd+1 < k) v[nd].calc(v[2*nd], v[2*nd+1]);
}
void add(int l, int r, ll x){
add(l, r, 1, 0, k/2-1, x, 0LL, 0);
}
ll sum(int l, int r, int nd, int a, int b, ll ex, bool tt){
if(a > r || b < l){
if(tt){
v[nd].lazy_assign = ex;
v[nd].lazy_add = 0LL;
v[nd].sm = (b-a+1)*ex;
v[nd].mn = ex;
v[nd].mx = ex;
}
else{
v[nd].lazy_add+=ex;
v[nd].sm+=(b-a+1)*ex;
v[nd].mn+=ex;
v[nd].mx+=ex;
}
return 0LL;
}
if(a >= l && b <= r){
if(tt){
v[nd].lazy_assign = ex;
v[nd].lazy_add = 0LL;
v[nd].sm = (b-a+1)*ex;
v[nd].mn = ex;
v[nd].mx = ex;
}
else{
v[nd].lazy_add+=ex;
v[nd].sm+=(b-a+1)*ex;
v[nd].mn+=ex;
v[nd].mx+=ex;
}
return v[nd].sm;
}
int md = (a+b)/2;
if(!tt){
ex+=v[nd].lazy_add;
if(v[nd].lazy_assign != -inf){
ex+=v[nd].lazy_assign;
tt = 1;
}
}
v[nd].lazy_add = 0LL;
v[nd].lazy_assign = -inf;
ll rt = sum(l, r, 2*nd, a, md, ex, tt) + sum(l, r, 2*nd+1, md+1, b, ex, tt);
if(2*nd+1 < k) v[nd].calc(v[2*nd], v[2*nd+1]);
return rt;
}
ll sum(int l, int r){
return sum(l, r, 1, 0, k/2-1, 0LL, 0);
}
};
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, m, q; cin >> n >> m >> q;
segtree seg(n);
while(q--){
int tt; cin >> tt;
if(tt == 1){
int l, r, c; ll k; cin >> l >> r >> c >> k; l--, r--;
seg.add(l, r, k);
}
else if(tt == 2){
int l, r; ll k; cin >> l >> r >> k; l--, r--;
seg.add(l, r, -k);
seg.chmx(0, seg.k/2-1, 0);
}
else{
int a; ll b; cin >> a >> b; a--;
cout << (seg.sum(a, a) >= b ? 1:0) << "\n";
}
}
}
Compilation message
foodcourt.cpp: In constructor 'segtree::segtree(int)':
foodcourt.cpp:25:9: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
25 | while(k <= n) k*=2; k*=2;
| ^~~~~
foodcourt.cpp:25:29: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
25 | while(k <= n) k*=2; k*=2;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
79 ms |
6636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
481 ms |
26408 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
76 ms |
6932 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
