#include<bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e18;
int n,m,q;
pair<pair<int,int>,pair<int,int>> aint[530000][3];
int lazy[530000][3];
pair<pair<int,int>,pair<int,int>> emp = {{INF,INF},{-INF,-INF}};
pair<pair<int,int>,pair<int,int>> combine(pair<pair<int,int>,pair<int,int>> x, pair<pair<int,int>,pair<int,int>> y)
{
return {min(x.first,y.first),max(x.second,y.second)};
}
void build(int nod, int st, int dr)
{
if(st==dr)
{
aint[nod][0] = aint[nod][1] = aint[nod][2] = {{0,st},{0,st}};
return;
}
int mij=(st+dr)/2;
build(nod*2,st,mij);
build(nod*2+1,mij+1,dr);
aint[nod][0] = combine(aint[nod*2][0], aint[nod*2+1][0]);
aint[nod][1] = combine(aint[nod*2][1], aint[nod*2+1][1]);
aint[nod][2] = combine(aint[nod*2][2], aint[nod*2+1][2]);
}
void propagate(int nod, int c)
{
if(!lazy[nod][c])
return;
lazy[nod*2][c]+=lazy[nod][c];
lazy[nod*2+1][c]+=lazy[nod][c];
aint[nod*2][c].first.first+=lazy[nod][c];
aint[nod*2][c].second.first+=lazy[nod][c];
aint[nod*2+1][c].first.first+=lazy[nod][c];
aint[nod*2+1][c].second.first+=lazy[nod][c];
lazy[nod][c]=0;
}
void upd(int nod, int st, int dr, int le, int ri, int newv, int c)
{
if(le>ri)
return;
if(le==st && dr==ri)
{
lazy[nod][c]+=newv;
aint[nod][c].first.first+=newv;
aint[nod][c].second.first+=newv;
return;
}
propagate(nod,c);
int mij=(st+dr)/2;
upd(nod*2,st,mij,le,min(mij,ri),newv,c);
upd(nod*2+1,mij+1,dr,max(mij+1,le),ri,newv,c);
aint[nod][c] = combine(aint[nod*2][c], aint[nod*2+1][c]);
}
pair<pair<int,int>,pair<int,int>> qry(int nod, int st, int dr, int le, int ri, int c)
{
if(le>ri)
return emp;
if(le==st && dr==ri)
return aint[nod][c];
propagate(nod,c);
int mij=(st+dr)/2;
return combine(qry(nod*2,st,mij,le,min(mij,ri),c),
qry(nod*2+1,mij+1,dr,max(mij+1,le),ri,c));
}
int cautare_binara(int nod, int st, int dr, int x)
{
if(st==dr)
{
if(aint[nod][1].first.first>=x)
return st;
else
return -1;
}
propagate(nod,1);
int mij=(st+dr)/2;
if(aint[nod*2][1].first.first>=x)
return cautare_binara(nod*2,st,mij,x);
else
return cautare_binara(nod*2+1,mij+1,dr,x);
}
vector<pair<int,int>> upds[250005];
vector<pair<int,int>> qrys[250005];
int rez[250005];
int cit[250005];
signed main()
{
ios_base::sync_with_stdio(0);cin.tie(0);
cin>>n>>m>>q;
int tip,le,ri,c,k,a,b;
for(int i=1;i<=q;i++)
{
cin>>tip;
rez[i] = -7;
if(tip==1)
{
cin>>le>>ri>>c>>k;
upds[le].push_back({i,k});
upds[ri+1].push_back({i,-k});
cit[i]=c;
}
else if(tip==2)
{
cin>>le>>ri>>k;
upds[le].push_back({-i,k});
upds[ri+1].push_back({-i,-k});
}
else
{
cin>>a>>b;
qrys[a].push_back({b,i});
}
}
build(1,0,q);
for(int i=1;i<=n;i++)
{
for(auto [t,newv]:upds[i])
{
if(t < 0)
{
t = -t;
upd(1,0,q,t,q,-newv,0);
upd(1,0,q,t,q,newv,2);
}
else
{
upd(1,0,q,t,q,newv,0);
upd(1,0,q,t,q,newv,1);
}
}
for(auto [x,t]:qrys[i])
{
pair<pair<int,int>,pair<int,int>> aux = qry(1,0,q,0,t,0);
int ult = aux.first.second;
int scazute = qry(1,0,q,t,t,2).first.first - qry(1,0,q,ult,ult,2).first.first;
int pref1 = qry(1,0,q,ult,ult,1).first.first;
int ans = cautare_binara(1,0,q,x+pref1+scazute);
if(ans==-1)
{
rez[t]=0;
}
else
{
rez[t]=cit[ans];
}
}
}
for(int i=1;i<=q;i++)
{
if(rez[i]==-7)
continue;
cout<<rez[i]<<"\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
12632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
12632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
122 ms |
31492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
554 ms |
87592 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
12632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
107 ms |
30800 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
12632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
12632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
