//#include<i_am_noob_orz>
#include<bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long
#define int ll
#define ull unsigned long long
#define pii pair<int,int>
#define X first
#define Y second
#define mod ((ll)1e9+7)
#define pb push_back
#define mp make_pair
#define abs(x) ((x)>0?(x):(-(x)))
#define F(n) Fi(i,n)
#define Fi(i,n) Fl(i,0,n)
#define Fl(i,l,n) for(int i=l;i<n;i++)
#define memres(a) memset(a,0,sizeof(a))
#define all(a) a.begin(),a.end()
#define sz(a) ((int)a.size())
#define ceiling(a,b) (((a)+(b)-1)/(b))
#define endl '\n'
#define bit_count(x) __builtin_popcountll((x))
#define ykh mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define jimmy_is_kind false
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> rbtree;
//#define LOCAL
#ifdef LOCAL
#define bug(...) cerr<<"#"<<__LINE__<<' '<<#__VA_ARGS__<<"- ", _do(__VA_ARGS__)
template<typename T> void _do(T && x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S&&...y) {cerr<<x<<", "; _do(y...);}
#define IOS()
#else
#define IOS() ios_base::sync_with_stdio(0), cin.tie(0)
#define endl '\n'
#define bug(...)
#endif
int add(int a,int b){return(a+b>=mod?a+b-mod:a+b);}
int sub(int a,int b){return(a<b?a+mod-b:a-b);}
int po(int a,int b){
if(b==0)return 1;
if(b==1)return(a%mod);
int tem=po(a,b/2);
if(b&1)return(((tem*tem)%mod)*a)%mod;
else return(tem*tem)%mod;
}
int GCD(int a,int b){
int x=0;
int ra,rb;
while(a&&b){
if(((a&1)==0)&&((b&1)==0)){
a>>=1,b>>=1,x++;
}
else if((a^b)&1){
if(a&1)b>>=1;
else a>>=1;
}
else{
ra=abs(a-b),rb=min(a,b);
a=ra,b=rb;
}
}
return max(a,b)<<x;
}
int gcd(int a,int b){if(b==0)return a;return gcd(b,a%b);}
int n,m,q;
struct segment_tree{
struct NODE{
vector<pii> ve;
queue<pii> tg;
int mi,v,tt;
NODE():mi(0),v(0),tt(0){}
int bs(int l,int r,int vl){
if(l==r){
return ve[l].Y;
}
int mi=(l+r)/2;
bug(mi,ve[mi].X,vl);
if(ve[mi].X>=vl)return bs(l,mi,vl);
else return bs(mi+1,r,vl);
}
}seg[1000010];
void push(int p){
while(!seg[p].tg.empty()){
if(seg[p].tg.front().Y==-1){
seg[p*2].mi=min(seg[p*2].v,seg[p*2].mi+seg[p].tg.front().X);
seg[p*2+1].mi=min(seg[p*2+1].v,seg[p*2+1].mi+seg[p].tg.front().X);
bug(p*2+1,seg[p*2+1].mi,seg[p].tg.front().X);
}
else{
seg[p*2].v+=seg[p].tg.front().X;
seg[p*2].ve.pb({seg[p*2].v,seg[p].tg.front().Y});
seg[p*2+1].v+=seg[p].tg.front().X;
seg[p*2+1].ve.pb({seg[p*2+1].v,seg[p].tg.front().Y});
}
seg[p*2].tg.push(seg[p].tg.front());
seg[p*2+1].tg.push(seg[p].tg.front());
seg[p].tg.pop();
}
}
void insert(int p,int l,int r,int ql,int qr,pii vl){
if(l>qr||r<ql)return;
if(l>=ql&&r<=qr){
seg[p].v+=vl.X;
seg[p].ve.pb({seg[p].v,vl.Y});
seg[p].tg.push(vl);
return;
}
int mi=(l+r)/2;
push(p);
insert(p*2,l,mi,ql,qr,vl);
insert(p*2+1,mi+1,r,ql,qr,vl);
return;
}
void erase(int p,int l,int r,int ql,int qr,int vl){
if(l>qr||r<ql)return;
if(l>=ql&&r<=qr){
seg[p].mi=min(seg[p].v,seg[p].mi+vl);
bug(seg[p].mi,seg[p].v);
seg[p].tg.push({vl,-1});
return;
}
int mi=(l+r)/2;
push(p);
erase(p*2,l,mi,ql,qr,vl);
erase(p*2+1,mi+1,r,ql,qr,vl);
return;
}
int qry(int p,int l,int r,int x,int vl){
if(l==r){
bug(p,seg[p].mi,vl,seg[p].v,sz(seg[p].ve)-1);
if(seg[p].mi+vl>seg[p].v)return 0;
else return seg[p].bs(0,sz(seg[p].ve)-1,seg[p].mi+vl);
}
int mi=(l+r)/2;
push(p);
if(mi>=x)return qry(p*2,l,mi,x,vl);
else return qry(p*2+1,mi+1,r,x,vl);
}
}sgt;
signed main(){
IOS();
cin>>n>>m>>q;
while(q--){
int ty;
cin>>ty;
if(ty==1){
int l,r,c,k;
cin>>l>>r>>c>>k;
--l,--r;
sgt.insert(1,0,n-1,l,r,{k,c});
}
else if(ty==2){
int l,r,k;
cin>>l>>r>>k;
--l,--r;
sgt.erase(1,0,n-1,l,r,k);
}
else{
int x,y;
cin>>x>>y;
--x;
cout<<sgt.qry(1,0,n-1,x,y)<<endl;
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
289 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
289 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
293 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
278 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
289 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
296 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
289 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
289 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
