#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll INF=1e17;
ll n,m,q;
struct date
{
ll tip,l,r,k,c;
} v[250005];
vector<int> ev[250005];
bool comp(int a, int b)
{
return v[a].tip<v[b].tip;
}
pll arbmin[4*250005];
ll arbmax[4*250005],arbsum[4*250005];
ll topropmin[4*250005],topropmax[4*250005],topropsum[4*250005];
ll sol[250005];
void buildmin(ll nod,ll st,ll dr)
{
arbmin[nod]={0,st};
if(st==dr)
return;
ll mij=(st+dr)/2;
buildmin(nod*2,st,mij);
buildmin(nod*2+1,mij+1,dr);
}
void propmin(ll nod)
{
ll val=topropmin[nod];
arbmin[nod*2].first+=val;
arbmin[nod*2+1].first+=val;
topropmin[nod*2]+=val;
topropmin[nod*2+1]=val;
}
void updatemin(ll nod,ll st,ll dr,ll a,ll b,ll val)
{
if(st<dr)
propmin(nod);
topropmin[nod]=0;
if(st>=a&&dr<=b)
{
arbmin[nod].first+=val;
topropmin[nod]+=val;
return;
}
ll mij=(st+dr)/2;
if(a<=mij)
updatemin(nod*2,st,mij,a,b,val);
if(b>mij)
updatemin(nod*2+1,mij+1,dr,a,b,val);
arbmin[nod]=min(arbmin[nod*2],arbmin[nod*2+1]);
}
pll querymin(ll nod,ll st,ll dr,ll a,ll b)
{
if(st<dr)
propmin(nod);
topropmin[nod]=0;
if(st>=a&&dr<=b)
return arbmin[nod];
pll rez={INF,INF};
ll mij=(st+dr)/2;
if(a<=mij)
rez=min(rez,querymin(nod*2,st,mij,a,b));
if(b>mij)
rez=min(rez,querymin(nod*2+1,mij+1,dr,a,b));
return rez;
}
void propmax(ll nod)
{
ll val=topropmax[nod];
arbmax[nod*2]+=val;
arbmax[nod*2+1]+=val;
topropmax[nod*2]+=val;
topropmax[nod*2+1]+=val;
}
void updatemax(ll nod,ll st,ll dr,ll a,ll b,ll val)
{
if(st<dr)
propmax(nod);
topropmax[nod]=0;
if(st>=a&&dr<=b)
{
arbmax[nod]+=val;
topropmax[nod]+=val;
return;
}
ll mij=(st+dr)/2;
if(a<=mij)
updatemax(nod*2,st,mij,a,b,val);
if(b>mij)
updatemax(nod*2+1,mij+1,dr,a,b,val);
arbmax[nod]=max(arbmax[nod*2],arbmax[nod*2+1]);
}
ll querymax(ll nod,ll st,ll dr,ll a,ll b)
{
if(st<dr)
propmax(nod);
topropmax[nod]=0;
if(st>=a&&dr<=b)
return arbmax[nod];
ll rez=0;
ll mij=(st+dr)/2;
if(a<=mij)
rez=max(rez,querymax(nod*2,st,mij,a,b));
if(b>mij)
rez=max(rez,querymax(nod*2+1,mij+1,dr,a,b));
return rez;
}
ll getfirst(ll nod,ll st,ll dr,ll val)
{
if(st<dr)
propmax(nod);
topropmax[nod]=0;
if(arbmax[nod]<val)
return INF;
if(st==dr)
return st;
ll mij=(st+dr)/2;
if(arbmax[nod*2]>=val)
return getfirst(nod*2,st,mij,val);
return getfirst(nod*2+1,mij+1,dr,val);
}
void updatesum(ll nod,ll st,ll dr,ll poz,ll val)
{
if(st==dr)
{
arbsum[nod]+=val;
return;
}
ll mij=(st+dr)/2;
if(poz<=mij)
updatesum(nod*2,st,mij,poz,val);
else
updatesum(nod*2+1,mij+1,dr,poz,val);
arbsum[nod]=arbsum[nod*2]+arbsum[nod*2+1];
}
ll querysum(ll nod,ll st,ll dr,ll a,ll b)
{
if(st>=a&&dr<=b)
return arbsum[nod];
ll mij=(st+dr)/2;
ll rez=0;
if(a<=mij)
rez+=querysum(nod*2,st,mij,a,b);
if(b>mij)
rez+=querysum(nod*2+1,mij+1,dr,a,b);
return rez;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m>>q;
for(int i=1;i<=q;i++)
{
cin>>v[i].tip;
if(v[i].tip==1)
{
cin>>v[i].l>>v[i].r>>v[i].c>>v[i].k;
ev[v[i].l].push_back(i);
ev[v[i].r+1].push_back(i);
}
if(v[i].tip==2)
{
cin>>v[i].l>>v[i].r>>v[i].k;
ev[v[i].l].push_back(i);
ev[v[i].r+1].push_back(i);
}
if(v[i].tip==3)
{
cin>>v[i].l>>v[i].k;
ev[v[i].l].push_back(i);
}
}
buildmin(1,1,q);
for(int z=1;z<=n;z++)
if(!ev[z].empty())
{
sort(ev[z].begin(),ev[z].end(),comp);
for(int i:ev[z])
{
if(v[i].tip==1)
{
if(z==v[i].l)
{
updatemin(1,1,q,i,q,v[i].k);
updatemax(1,1,q,i,q,v[i].k);
}
else
{
updatemin(1,1,q,i,q,-v[i].k);
updatemax(1,1,q,i,q,-v[i].k);
}
}
if(v[i].tip==2)
{
if(z==v[i].l)
{
updatemin(1,1,q,i,q,-v[i].k);
updatesum(1,1,q,i,-v[i].k);
}
else
{
updatemin(1,1,q,i,q,v[i].k);
updatesum(1,1,q,i,v[i].k);
}
}
if(v[i].tip==3)
{
ll b=v[i].k;
pll p=querymin(1,1,q,1,i);
ll st=1;
ll dr=i;
if(p.first<0)
st=p.second+1;
if(st>dr)
{
sol[i]=0;
continue;
}
ll x=querysum(1,1,q,st,dr);
b-=x;
if(st-1>0)
b+=querymax(1,1,q,1,st-1);
ll poz=getfirst(1,1,q,b);
if(poz<=dr)
sol[i]=v[poz].c;
}
}
}
for(int i=1;i<=q;i++)
if(v[i].tip==3)
cout<<sol[i]<<'\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
14940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
14940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
84 ms |
25504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
458 ms |
62832 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
14940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
80 ms |
25856 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
14940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
14940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
