#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#define ll long long
#define pii pair<ll,ll>
#define pll pair<ll,ll>
#define plx pair<ll,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vl vector<ll>
#define vvi vector<vi>
using namespace std;
const int mxn=500;
struct fenw{
ll a[mxn]{0};
void add(int i,ll amt){
for(;i<mxn;i+=i&-i)a[i]+=amt;
}
ll qr(int l,int r,ll res=0){
for(;r;r-=r&-r)res+=a[r];
for(l--;l;l-=l&-l)res-=a[l];
return res;
}
}fw[2];
struct lazy{
pll t[4*mxn];ll lz[4*mxn]{0};
void build(int i,int l,int r){
if(l==r)return void(t[i]={0,l});
int m=(l+r)>>1;
build(2*i,l,m);build(2*i+1,m+1,r);
t[i]=min(t[2*i],t[2*i+1]);
}
void push(int i,int l,int r){
t[i].f+=lz[i];
if(l<r)lz[2*i]+=lz[i],lz[2*i+1]+=lz[i];
lz[i]=0;
}
void upd(int i,int l,int r,int tl,int tr,ll v){
push(i,l,r);
if(r<tl||l>tr)return;
if(r<=tr&&l>=tl){
lz[i]+=v;push(i,l,r);return;
}int m=(l+r)>>1;upd(2*i,l,m,tl,tr,v);upd(2*i+1,m+1,r,tl,tr,v);
t[i]=min(t[2*i],t[2*i+1]);
}
pll qr(int i,int l,int r,int tl,int tr){
push(i,l,r);
if(r<tl||l>tr)return {1e9,1e9};
if(r<=tr&&l>=tl)return t[i];
int m=(l+r)>>1;
return min(qr(2*i,l,m,tl,tr),qr(2*i+1,m+1,r,tl,tr));
}
}sg;
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
int n,m,q;cin>>n>>m>>q;int g[q+1];
vector<pair<int,pii>>vec[n+2];vector<pii>ask[n+1];
for(int i=1;i<=q;i++){
int t;cin>>t;
if(t==1){int l,r,k;cin>>l>>r>>g[i]>>k;vec[l].pb({0,{i,k}}),vec[r+1].pb({0,{i,-k}});}
else if(t==2){int l,r,k;cin>>l>>r>>k;vec[l].pb({1,{i,k}}),vec[r+1].pb({1,{i,-k}});}
else {int a,b;cin>>a>>b;ask[a].pb({b,i});}
}sg.build(1,0,q);
int ans[q+1];for(int i=1;i<=q;i++)ans[i]=-1;
for(int i=1;i<=n;i++){
for(auto it : vec[i]){
if(it.f==0){sg.upd(1,0,q,it.s.f,q,it.s.s);fw[0].add(it.s.f,it.s.s);}
else {sg.upd(1,0,q,it.s.f,q,-it.s.s);fw[1].add(it.s.f,it.s.s);}
}
for(auto it : ask[i]){
int st=sg.qr(1,0,q,0,it.s).s;st++;ll tt=it.f+fw[1].qr(st,it.s);
if(fw[0].qr(st,it.s)<tt){ans[it.s]=0;continue;}
int l=st,r=it.s;
while(l<r){
int md=(l+r)>>1;
if(fw[0].qr(st,md)>=tt)r=md;
else l=md+1;
}ans[it.s]=g[l];
}
}
for(int i=1;i<=q;i++)if(ans[i]!=-1)cout<<ans[i]<<'\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
980 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
980 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
26 ms |
15452 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
23 ms |
31196 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
980 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
9176 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
980 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
980 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
