#include <bits/stdc++.h>
#define INF 10000000000000000
using namespace std;
struct wow
{
long long minimpar,minpar,maximpar,maximimpar;
}arb[800005];
long long lazy[800005];
void construieste (int st,int dr,int nod ,int poz ,long long val)
{
if (st==dr)
{
if (val%2==1)
{
arb[nod].minimpar=arb[nod].maximimpar=val;
arb[nod].minpar=INF;
arb[nod].maximpar=-INF;
}
else
{
arb[nod].minpar=arb[nod].maximpar=val;
arb[nod].minimpar=INF;
arb[nod].maximimpar=-INF;
}
return ;
}
int mij=(st+dr)/2;
if (mij>=poz)
{
construieste(st,mij,2*nod,poz,val);
}
else
{
construieste(mij+1,dr,2*nod+1,poz,val);
}
arb[nod].maximpar=max(arb[2*nod].maximpar,arb[2*nod+1].maximpar);
arb[nod].minpar=min(arb[2*nod].minpar,arb[2*nod+1].minpar);
arb[nod].maximimpar=max(arb[2*nod].maximimpar,arb[2*nod+1].maximimpar);
arb[nod].minimpar=min(arb[2*nod].minimpar,arb[2*nod+1].minimpar);
}
void aduna (int nod,int val)
{
if (arb[nod].minimpar!=INF)
{
arb[nod].minimpar+=val;
}
if (arb[nod].minpar!=INF)
{
arb[nod].minpar+=val;
}
if (arb[nod].maximimpar!=-INF)
{
arb[nod].maximimpar+=val;
}
if (arb[nod].maximpar!=-INF)
{
arb[nod].maximpar+=val;
}
if (val%2==1)
{
swap(arb[nod].minpar,arb[nod].minimpar);
swap(arb[nod].maximimpar,arb[nod].maximpar);
}
}
void propaga (int st,int dr,int nod)
{
if (st>dr||lazy[nod]==0)
{
return;
}
lazy[2*nod+1]+=lazy[nod];
lazy[2*nod]+=lazy[nod];
aduna(2*nod,lazy[nod]);
aduna(2*nod+1,lazy[nod]);
lazy[nod]=0;
}
void update (int st,int dr,int nod,int ua,int ub,long long val)
{
if (ua<=st&&dr<=ub)
{
lazy[nod]+=val;
aduna(nod,val);
return ;
}
propaga(st,dr,nod);
int mij=(st+dr)/2;
if (ua<=mij)
{
update (st,mij,2*nod,ua,ub,val);
}
if (mij<ub)
{
update (mij+1,dr,2*nod+1,ua,ub,val);
}
arb[nod].maximpar=max(arb[2*nod].maximpar,arb[2*nod+1].maximpar);
arb[nod].minpar=min(arb[2*nod].minpar,arb[2*nod+1].minpar);
arb[nod].maximimpar=max(arb[2*nod].maximimpar,arb[2*nod+1].maximimpar);
arb[nod].minimpar=min(arb[2*nod].minimpar,arb[2*nod+1].minimpar);
}
long long minim,maxim;
void query (int st,int dr,int nod ,int ua ,int ub,int tip)
{
if (ua<=st&&dr<=ub)
{
if (tip==0)
{
minim=min(minim,arb[nod].minpar);
}
else
{
maxim=max(maxim,arb[nod].maximimpar);
}
return;
}
propaga(st,dr,nod);
int mij=(st+dr)/2;
if (ua<=mij)
{
query (st,mij,2*nod,ua,ub,tip);
}
if (mij<ub)
{
query (mij+1,dr,2*nod+1,ua,ub,tip);
}
}
int n,i,x,m,tip;
long long a,b,val;
int main()
{
ios_base :: sync_with_stdio(false);
cin.tie(0);
#ifdef HOME
ifstream cin("date.in");
ofstream cout("date.out");
#endif // HOME
cin>>n;
for (i=1;i<=n;i++)
{
cin>>x;
construieste(1,n,1,i,x);
}
cin>>m;
for (i=1;i<=m;i++)
{
cin>>tip;
if (tip==0)
{
cin>>a>>b>>val;
update(1,n,1,a,b,val);
}
else
{
cin>>a>>b;
minim=INF;
query(1,n,1,a,b,0);
if (minim==INF)
{
cout<<"-1"<<' ';
}
else
{
cout<<minim<<' ';
}
maxim=-INF;
query(1,n,1,a,b,1);
if (maxim==-INF)
{
cout<<"-1"<<'\n';
}
else
{
cout<<maxim<<'\n';
}
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
768 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
164 ms |
10360 KB |
Output is correct |
| 2 |
Correct |
366 ms |
20216 KB |
Output is correct |
| 3 |
Correct |
354 ms |
20216 KB |
Output is correct |
| 4 |
Correct |
366 ms |
20356 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
768 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
