#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 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 node{
ll s,s1,s2;
ll mnpref;
ll mxpref;
node(){
s=0,s1=0,s2=0;
mnpref=mxpref=0;
}
};
node mg(node a,node b){
node c;
c.s=a.s+b.s;
c.s1=a.s1+b.s1;
c.s2=a.s2+b.s2;
c.mnpref=min({a.mnpref,b.mnpref+a.s});
c.mxpref=max({a.mxpref,b.mxpref+a.s1});
return c;
}
struct sega{
node t[4*N];
void upd(int i,ll x,int tp,int v,int tl,int tr){
if(tl==tr){
t[v].s+=tp*x;
if(x<0) t[v].s2+=tp*-x;
else t[v].s1+=tp*x;
t[v].mnpref=t[v].s;
t[v].mxpref=t[v].s1;
// umax(t[v].mxpref,0LL);
// umin(t[v].mnpref,0LL);
// cout<<"E "<<tl<<' '<<tr<<' '<<t[v].s2<<' '<<t[v]endl;
return;
}
int tm=(tl+tr)>>1;
if(tm>=i)
upd(i,x,tp,v<<1,tl,tm);
else
upd(i,x,tp,v<<1|1,tm+1,tr);
t[v]=mg(t[2*v],t[2*v+1]);
}
int findj(ll x,int i,int v,int tl,int tr){
if(tl>i) return -1;
if(tr<=i){
if((x+t[v].mnpref)>=0)
return -1;
}
if(tl==tr) return tl;
int tm=(tl+tr)>>1;
int j=findj(x+t[2*v].s,i,2*v+1,tm+1,tr);
if(j==-1)
return findj(x,i,2*v,tl,tm);
return j;
}
int findj1(ll x,int i,ll wt,int v,int tl,int tr){
if(tr<i)
return -1;
// cout<<"V "<<v<<' '<<tl<<' '<<tr<<' '<<t[v].s1<<' '<<t[v].mxpref<<endl;
if(tl>=i){
if((x+t[v].mxpref)<wt)
return -1;
}
if(tl==tr) return tl;
int tm=(tl+tr)>>1;
int j=findj1(x,i,wt,2*v,tl,tm);
if(j!=-1) return j;
return findj1(x+t[2*v].s1,i,wt,2*v+1,tm+1,tr);
}
node emp;
node gets(int l,int r,int v,int tl,int tr){
// cout<<l<<' '<<r<<' '<<"TL "<<tl<<' '<<tr<<' '<<t[v].s<<endl;
if(tl>=l&&tr<=r)
return t[v];
if(tl>r||tr<l)
return emp;
int tm=(tl+tr)>>1;
return mg(gets(l,r,2*v,tl,tm),gets(l,r,2*v+1,tm+1,tr));
}
}sega;
signed main(){
fast_prep;
int n,m,q;
cin>>n>>m>>q;
vec<int> t(q),l(q),r(q),c(q);
vec<ll>k(q);
vec<vec<int>> rs(n,vec<int>());
vec<vec<int>> ls(n,vec<int>());
vec<vec<int>> asks(n,vec<int>());
vec<int>ans(q);
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];
ls[l[i]].pb(i);
rs[r[i]].pb(i);
// sega.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];
ls[l[i]].pb(i);rs[r[i]].pb(i);
// fen.add(l[i],r[i],k[i]);
// sega.add(l[i],r[i],-k[i],i,1,0,n-1);
}
else{
cin>>l[i]>>k[i];
--l[i];
asks[l[i]].pb(i);
}
}
vec<int> ids(q);
for(int i=0;i<n;i++){
for(auto &j : ls[i]){
if(t[j]==1) sega.upd(j,k[j],1,1,0,q-1);
else sega.upd(j,-k[j],1,1,0,q-1);
}
for(auto &j : asks[i]){
int f=sega.findj(0,j,1,0,q-1);
++f;
node that=sega.gets(0,f-1,1,0,q-1);
ll toadd=-that.s;
ll need=sega.gets(0,j,1,0,q-1).s2+k[j];
int s=sega.findj1(toadd,f,need,1,0,q-1);
if(s==-1 || s>=j) ans[j]=0;
else ans[j]=c[s];
}
for(auto &j : rs[i]){
if(t[j]==1) sega.upd(j,k[j],-1,1,0,q-1);
else sega.upd(j,-k[j],-1,1,0,q-1);
}
}
for(int i=0;i<q;i++){
if(t[i]==3) cout<<ans[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 3
1 2 3 5 2
1 1 2 2 4
3 2 3
2 1 3 3
3 1 2
1 2 3 4 2
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
47444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
47444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
160 ms |
58064 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
529 ms |
84744 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
47444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
103 ms |
57172 KB |
Output is correct |
| 2 |
Correct |
109 ms |
56976 KB |
Output is correct |
| 3 |
Correct |
127 ms |
57912 KB |
Output is correct |
| 4 |
Correct |
84 ms |
55852 KB |
Output is correct |
| 5 |
Correct |
102 ms |
56840 KB |
Output is correct |
| 6 |
Correct |
111 ms |
57804 KB |
Output is correct |
| 7 |
Correct |
71 ms |
51404 KB |
Output is correct |
| 8 |
Correct |
72 ms |
51220 KB |
Output is correct |
| 9 |
Correct |
92 ms |
56884 KB |
Output is correct |
| 10 |
Correct |
82 ms |
54992 KB |
Output is correct |
| 11 |
Correct |
100 ms |
57096 KB |
Output is correct |
| 12 |
Correct |
101 ms |
57108 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
47444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
47444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
