#include <bits/stdc++.h>
using namespace std;
long long n,q,ai1[1000005],ai2[1000005],ai3[1000005],ai4[1000005],lazy[1000005],v[200005];
const long long oo = 1LL*INT_MAX*INT_MAX;
void propag(long long nod, long long a, long long b)
{
if(a==b || lazy[nod]==0)
return;
lazy[nod*2]+=lazy[nod];
lazy[nod*2+1]+=lazy[nod];
if(ai1[nod*2]!=oo)
ai1[nod*2]+=lazy[nod];
if(ai1[nod*2+1]!=oo)
ai1[nod*2+1]+=lazy[nod];
if(ai2[nod*2]!=oo)
ai2[nod*2]+=lazy[nod];
if(ai2[nod*2+1]!=oo)
ai2[nod*2+1]+=lazy[nod];
if(ai3[nod*2]!=-oo)
ai3[nod*2]+=lazy[nod];
if(ai3[nod*2+1]!=-oo)
ai3[nod*2+1]+=lazy[nod];
if(ai4[nod*2]!=-oo)
ai4[nod*2]+=lazy[nod];
if(ai4[nod*2+1]!=-oo)
ai4[nod*2+1]+=lazy[nod];
if(lazy[nod]%2)
{
swap(ai1[nod*2],ai2[nod*2]);
swap(ai1[nod*2+1],ai2[nod*2+1]);
swap(ai3[nod*2],ai4[nod*2]);
swap(ai4[nod*2+1],ai4[nod*2+1]);
}
lazy[nod]=0;
}
void update(long long ua, long long ub, long long val, long long nod, long long a, long long b)
{
if(ua<=a && ub>=b)
{
lazy[nod]+=val;
if(ai1[nod]!=oo)
ai1[nod]+=val;
if(ai2[nod]!=oo)
ai2[nod]+=val;
if(ai3[nod]!=-oo)
ai3[nod]+=val;
if(ai4[nod]!=-oo)
ai4[nod]+=val;
if(val%2)
{
swap(ai1[nod],ai2[nod]);
swap(ai3[nod],ai4[nod]);
}
return;
}
propag(nod,a,b);
long long mij=(a+b)/2;
if(ua<=mij)
{
update(ua,ub,val,nod*2,a,mij);
}
if(ub>mij)
{
update(ua,ub,val,nod*2+1,mij+1,b);
}
ai1[nod]=min(ai1[nod*2],ai1[nod*2+1]);
ai2[nod]=min(ai2[nod*2],ai2[nod*2+1]);
ai3[nod]=max(ai3[nod*2],ai3[nod*2+1]);
ai4[nod]=max(ai4[nod*2],ai4[nod*2+1]);
}
pair<long long,long long> query(long long qa, long long qb, long long nod, long long a, long long b)
{
if(qa<=a && qb>=b)
{
return {ai1[nod],ai3[nod]};
}
propag(nod,a,b);
long long mij=(a+b)/2;
pair<long long,long long> rez1={oo,-oo},rez2={oo,-oo};
if(qa<=mij)
{
rez1=query(qa,qb,nod*2,a,mij);
}
if(qb>mij)
{
rez2=query(qa,qb,nod*2+1,mij+1,b);
}
return {min(rez1.first,rez2.first),max(rez1.second,rez2.second)};
}
void update_in(long long poz, long long val, long long nod, long long a, long long b)
{
if(a==b)
{
if(val%2==0)
{
ai1[nod]=ai4[nod]=val;
ai2[nod]=oo;
ai3[nod]=-oo;
}
else if(val%2==1)
{
ai2[nod]=ai3[nod]=val;
ai1[nod]=oo;
ai4[nod]=-oo;
}
return;
}
long long mij=(a+b)/2;
if(poz<=mij)
{
update_in(poz,val,nod*2,a,mij);
}
else
{
update_in(poz,val,nod*2+1,mij+1,b);
}
ai1[nod]=min(ai1[nod*2],ai1[nod*2+1]);
ai2[nod]=min(ai2[nod*2],ai2[nod*2+1]);
ai3[nod]=max(ai3[nod*2],ai3[nod*2+1]);
ai4[nod]=max(ai4[nod*2],ai4[nod*2+1]);
}
int main()
{
// freopen("hard.in","r",stdin);
// freopen("hard.out","w",stdout);
///1 for minimum even number
///2 for minimum odd number
///3 for maximum odd number
///4 for maximum even number
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
for(long long i=1;i<=n;i++)
{
cin>>v[i];
update_in(i,v[i],1,1,n);
}
cin>>q;
for(long long i=1;i<=q;i++)
{
long long t,a,b,val;
cin>>t;
if(t==0)
{
cin>>a>>b>>val;
if(a>b)
continue;
update(a,b,val,1,1,n);
}
else if(t==1)
{
cin>>a>>b;
if(a>b)
{
cout<<"-1 -1"<<'\n';
}
pair<long long,long long> rez=query(a,b,1,1,n);
if(rez.first==oo)
{
cout<<-1<<' ';
}
else
{
cout<<rez.first<<' ';
}
if(rez.second==-oo)
{
cout<<-1<<'\n';
}
else
{
cout<<rez.second<<'\n';
}
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
768 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
129 ms |
11128 KB |
Output is correct |
| 2 |
Correct |
285 ms |
22136 KB |
Output is correct |
| 3 |
Correct |
291 ms |
21936 KB |
Output is correct |
| 4 |
Correct |
292 ms |
21880 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
768 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
