#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ii pair<ll,ll>
#define fi first
#define se second
#define endl '\n'
#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound
#define rep(x,s,e) for (auto x=s-(s>e);x!=e-(s>e);s<e?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll INF=1e18;
struct node{
int s,e,m;
ll val=0,lazy=0;
node *l,*r;
node (int _s,int _e){
s=_s,e=_e,m=s+e>>1;
if (s!=e){
l=new node(s,m);
r=new node(m+1,e);
}
}
void propo(){
if (lazy){
val+=lazy;
if (s!=e){
l->lazy+=lazy;
r->lazy+=lazy;
}
lazy=0;
}
}
void update(int i,int j,ll k){
if (s==i && e==j) lazy+=k;
else{
if (j<=m) l->update(i,j,k);
else if (m<i) r->update(i,j,k);
else l->update(i,m,k),r->update(m+1,j,k);
l->propo(),r->propo();
val=min(l->val,r->val);
}
}
ll query(int i,int j){
propo();
if (s==i && e==j) return val;
else if (j<=m) return l->query(i,j);
else if (m<i) return r->query(i,j);
else return min(l->query(i,m),r->query(m+1,j));
}
} *root=new node(0,250005);
struct upd{
ll pos,t;
ll num;
};
int n,m,q;
vector<upd> u;
vector<ii> qu[250005]; //(length,time)
ll ans[250005];
int main(){
cin.tie(0);
cout.tie(0);
cin.sync_with_stdio(false);
memset(ans,-1,sizeof(ans));
cin>>n>>m>>q;
ll a,b,c,d;
rep(x,0,q){
cin>>a;
if (a==1){
cin>>a>>b>>c>>d;
u.pub(upd({a,x,d}));
u.pub(upd({b+1,x,-d}));
}
else if (a==2){
cin>>a>>b>>c;
u.pub(upd({a,x,-c}));
u.pub(upd({b+1,x,c}));
}
else{
cin>>a>>b;
qu[a].pub(ii(b,x));
}
}
sort(all(u),[](upd i,upd j){
return i.pos>j.pos;
});
rep(x,1,n+1){
while (!u.empty() && u.back().pos==x){
//cout<<"update: "<<u.back().t<<" "<<u.back().num<<endl;
root->update(u.back().t,250005,u.back().num);
u.pob();
}
for (auto &it:qu[x]){
ll num=root->query(it.se,it.se)-root->query(0,it.se);
if (num<it.fi) ans[it.se]=0;
else ans[it.se]=1;
}
}
rep(x,0,q) if (ans[x]!=-1) cout<<ans[x]<<endl;
}
Compilation message
foodcourt.cpp: In constructor 'node::node(int, int)':
foodcourt.cpp:31:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
31 | s=_s,e=_e,m=s+e>>1;
| ~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
32 ms |
39620 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
32 ms |
39620 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
131 ms |
43000 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
543 ms |
53680 KB |
Output is correct |
| 2 |
Correct |
478 ms |
47000 KB |
Output is correct |
| 3 |
Correct |
655 ms |
53648 KB |
Output is correct |
| 4 |
Correct |
466 ms |
53008 KB |
Output is correct |
| 5 |
Incorrect |
453 ms |
53024 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
32 ms |
39620 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
118 ms |
41708 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
32 ms |
39620 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
32 ms |
39620 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
