#include <bits/stdc++.h>
#define f first
#define s second
#define m_p make_pair
#define vec vector
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define sz(x) (int)(x).size()
#define pw(x) (1LL<<(x))
#define fast_prep ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
////#define int long long
//#pragma GCC optimize("unroll-loops")
using namespace std;
typedef long long ll;
const ll inf=1e18;
const int N=3e5+1;
template<class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
template<class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
struct fenwick{
ll fnw[N];
fenwick(){
fill(fnw,fnw+N,0);
}
void reset(){
fill(fnw,fnw+N,0);
}
void upd(int i,int x){
++i;
while(i<N){
fnw[i]+=x;
i+=i&-i;
}
}
ll get(int i){
++i;
ll ans=0;
while(i>0){
ans+=fnw[i];
i-=i&-i;
}
return ans;
}
void add(int l,int r,ll x){
upd(l,x);
upd(r+1,-x);
}
};
struct segtree{
ll p1[4*N];
int p3[4*N];
struct node{
ll x,y;
node(){
x=0,y=inf;
}
};
node mg(node a,node b){
if(a.x>b.x) swap(a.x,b.x);
if(b.x>b.y) swap(b.x,b.y);
if(a.x==b.x) umin(a.y,b.y);
else umin(a.y,b.x);
return a;
}
node tt[4*N];
segtree(){
fill(p1,p1+4*N,0);
fill(p3,p3+4*N,-1);
}
void push(int v,int tl,int tr){
for(auto &u : {v<<1,v<<1|1}){
tt[u].x+=p1[v];
tt[u].y+=p1[v];
if(umax(tt[u].x,0LL)){
umax(p3[u],p3[v]);
}
p1[u]+=p1[v];
}
p1[v]=0;
}
bool check(ll a,ll b,ll c){
if((a+c)<=0 && (b+c)<=0)
return 0;
return 1;
}
void add(int l,int r,int x,int t,int v,int tl,int tr){
if(tl>r||tr<l) return;
if(tl>=l&&tr<=r&&check(tt[v].x,tt[v].y,x)){
tt[v].x+=x;tt[v].y+=x;
p1[v]+=x;
if(umax(tt[v].x,0LL)){
umax(p3[v],t);
}
return;
}
int tm=(tl+tr)>>1;push(v,tl,tr);
add(l,r,x,t,v<<1,tl,tm);add(l,r,x,t,v<<1|1,tm+1,tr);
tt[v]=mg(tt[2*v],tt[2*v+1]);
}
int get(int i,int v,int tl,int tr){
if(tl==tr)
return p3[v];
int tm=(tl+tr)>>1;push(v,tl,tr);
if(tm>=i)
return get(i,v<<1,tl,tm);
else
return get(i,v<<1|1,tm+1,tr);
}
}sega1;
signed main(){
fast_prep;
int n,m,q;
cin>>n>>m>>q;
fenwick fen;
vec<int> tl(q),tr(q);
vec<int> t(q),l(q),r(q),c(q);
vec<ll> k(q);
vec<int> ask;
vec<ll> rl(q);
vec<ll> toadd(q);
vec<vec<int>> need(q,vec<int>());
for(int i=0;i<q;i++){
cin>>t[i];
if(t[i]==1){
cin>>l[i]>>r[i]>>c[i]>>k[i];
--l[i];--r[i];
sega1.add(l[i],r[i],k[i],i,1,0,n-1);
}
else if(t[i]==2){
cin>>l[i]>>r[i]>>k[i];
--l[i];--r[i];
fen.add(l[i],r[i],k[i]);
sega1.add(l[i],r[i],-k[i],i,1,0,n-1);
}
else{
ask.pb(i);
cin>>l[i]>>k[i];
--l[i];
rl[i]=fen.get(l[i])+k[i];
// cerr<<"WO "<<sega.get(l[i],1,0,n-1);
tl[i]=sega1.get(l[i],1,0,n-1)+1;tr[i]=i;
if(tl[i]!=0) need[tl[i]-1].pb(i);
}
}
{
fen.reset();
for(int i=0;i<q;i++){
if(t[i]==1) fen.add(l[i],r[i],k[i]);
else if(t[i]==2) fen.add(l[i],r[i],-k[i]);
for(auto &j : need[i]){
toadd[j]=-fen.get(l[j]);
}
}
}
if(m==1){
fen.reset();
for(int i=0;i<q;i++){
if(t[i]==1) fen.add(l[i],r[i],k[i]);
else if(t[i]==3){
if((fen.get(l[i])+toadd[i])>=rl[i]){
cout<<1<<'\n';
}
else{
cout<<0<<'\n';
}
}
}
return 0;
}
int ok=1;
while(ok){
ok=0;
fen.reset();
vec<vec<int>> toask(q,vec<int>());
///just an id
for(auto &i : ask){
if(tl[i]!=tr[i]){
int tm=(tl[i]+tr[i])>>1;
// cout<<"HEYASK "<<i<<' '<<tl[i]<<' '<<tr[i]<<' '<<tm<<endl;
ok=1;
toask[tm].pb(i);
}
}
if(!ok) break;
for(int i=0;i<q;i++){
if(t[i]==1){
fen.add(l[i],r[i],k[i]);
}
// cout<<"I "<<i<<endl;
for(auto &j : toask[i]){
ll have=fen.get(l[j])+toadd[j];
// cout<<"YO "<<c[i]<<' '<<j<<' '<<have<<' '<<rl[j]<<endl;
if(have>=rl[j]){
tr[j]=i;
}
else{
tl[j]=i+1;
}
}
}
}
for(auto &i : ask){
cout<<(tl[i]==i?0:c[tl[i]])<<'\n';
}
return 0;
}
/*
3 5 5
1 2 3 5 2
1 1 2 2 4
2 1 3 3
1 2 3 4 2
3 3 2
3 5 5
1 2 3 5 2
1 1 2 2 4
2 1 3 3
3 1 2
1 2 3 4 2
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
35668 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
35668 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
118 ms |
42516 KB |
Output is correct |
| 2 |
Correct |
137 ms |
42344 KB |
Output is correct |
| 3 |
Correct |
124 ms |
42556 KB |
Output is correct |
| 4 |
Correct |
115 ms |
42488 KB |
Output is correct |
| 5 |
Correct |
132 ms |
42332 KB |
Output is correct |
| 6 |
Correct |
133 ms |
42328 KB |
Output is correct |
| 7 |
Correct |
57 ms |
41944 KB |
Output is correct |
| 8 |
Correct |
55 ms |
42144 KB |
Output is correct |
| 9 |
Correct |
111 ms |
42248 KB |
Output is correct |
| 10 |
Correct |
124 ms |
42328 KB |
Output is correct |
| 11 |
Correct |
114 ms |
42240 KB |
Output is correct |
| 12 |
Correct |
115 ms |
42276 KB |
Output is correct |
| 13 |
Incorrect |
116 ms |
41836 KB |
Output isn't correct |
| 14 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
483 ms |
52852 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
35668 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
151 ms |
41948 KB |
Output is correct |
| 2 |
Correct |
166 ms |
42676 KB |
Output is correct |
| 3 |
Correct |
168 ms |
42644 KB |
Output is correct |
| 4 |
Correct |
122 ms |
40544 KB |
Output is correct |
| 5 |
Correct |
146 ms |
41744 KB |
Output is correct |
| 6 |
Correct |
177 ms |
42776 KB |
Output is correct |
| 7 |
Correct |
129 ms |
41836 KB |
Output is correct |
| 8 |
Correct |
112 ms |
41532 KB |
Output is correct |
| 9 |
Correct |
132 ms |
42684 KB |
Output is correct |
| 10 |
Correct |
121 ms |
40456 KB |
Output is correct |
| 11 |
Correct |
169 ms |
42640 KB |
Output is correct |
| 12 |
Correct |
162 ms |
42672 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
35668 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
35668 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
