#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
//#include<bits/extc++.h>
//__gnu_pbds
struct SegTree{
struct node{
int Minn = 0;
int SMinn = (1e18);
int maxtag= -1;
int addtag = 0;
void add(int v){
addtag +=v;
Minn+=v;
if(SMinn<1e18) SMinn+=v;
}
void chmax(int v){
if(v<=Minn) return;
addtag = max(v,addtag);
maxtag = v;
Minn = v;
}
};
node merge(node a,node b){
node re;
re.Minn = min(a.Minn,b.Minn);
if(a.Minn == b.Minn){
re.SMinn = min(a.SMinn,b.SMinn);
}else if(a.Minn<b.Minn){
re.SMinn = min(a.SMinn,b.Minn);
}else{
re.SMinn = min(b.SMinn,a.Minn);
}
return re;
}
vector<node> arr;
int n;
void init(int _n){
n = _n;
arr.resize(4*n) ;
}
void push(int ind){
if(arr[ind].addtag){
if(2*ind<4*n) arr[2*ind].add(arr[ind].addtag);
if(2*ind+1<4*n) arr[2*ind+1].add(arr[ind].addtag);
}
arr[ind].addtag=0;
if(arr[ind].maxtag!=-1){
if(2*ind<4*n) arr[2*ind].chmax(arr[ind].maxtag);
if(2*ind+1<4*n) arr[2*ind+1].chmax(arr[ind].maxtag);
}
arr[ind].maxtag=-1;
}
void built(int ind,int L,int R){
if(L==R) return;
int M = (L+R)/2;
built(2*ind,L,M);
built(2*ind,M+1,R);
arr[ind] = merge(arr[2*ind],arr[2*ind+1]);
}
void Radd(int ind,int l,int r,int L,int R,int v){
//cout<<l<<" "<<r<<" "<<L<<" "<<R<<endl;
push(ind);
if(L==l && r==R){
arr[ind].add(v);
return;
}
int M = (L+R)/2;
if(r<=M) Radd(2*ind,l,r,L,M,v);
else if(l>M) Radd(2*ind+1,l,r,M+1,R,v);
else{
Radd(2*ind,l,M,L,M,v);
Radd(2*ind+1,M+1,r,M+1,R,v);
}
arr[ind] = merge(arr[2*ind],arr[2*ind+1]);
}
void Rchmax(int ind,int l,int r,int L,int R,int v){
//cout<<l<<" "<<r<<" "<<L<<" "<<R<<endl;
push(ind);
if(l==L && r==R && v<arr[ind].SMinn){
assert(arr[ind].addtag==0);
arr[ind].chmax(v);
return;
}
int M = (L+R)/2;
if(r<=M) Rchmax(2*ind,l,r,L,M,v);
else if(l>M) Rchmax(2*ind+1,l,r,M+1,R,v);
else{
Rchmax(2*ind,l,M,L,M,v);
Rchmax(2*ind+1,M+1,r,M+1,R,v);
}
arr[ind] = merge(arr[2*ind],arr[2*ind+1]);
}
int query(int ind,int x,int L,int R){
push(ind);
if(L==R) return arr[ind].Minn;
arr[ind] = merge(arr[2*ind],arr[2*ind+1]);
int M = (L+R)/2;
if(x<=M) return query(2*ind,x,L,M);
else return query(2*ind+1,x,M+1,R);
}
} seg;
signed main(){
ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n,m,q;cin>>n>>m>>q;
seg.init(n);
seg.built(1,1,n);
while(q--){
int t;cin>>t;
if(t==1){
int l,r,c,k;cin>>l>>r>>c>>k;
seg.Radd(1,l,r,1,n,k);
}
if(t==2){
int l,r,k;cin>>l>>r>>k;
seg.Radd(1,l,r,1,n,-k);
seg.Rchmax(1,l,r,1,n,0);
}
if(t==3){
int a,b;cin>>a>>b;
int g = seg.query(1,a,1,n);
//cout<<g<<"\n";
cout<<(g>=b)<<"\n";
}
}
return 0;
}
// segment tree beats + parellal binary search
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
73 ms |
8636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
309 ms |
28676 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
44 ms |
8284 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
