#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 bignumber = 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]!=bignumber)
ai1[nod*2]+=lazy[nod];
if(ai1[nod*2+1]!=bignumber)
ai1[nod*2+1]+=lazy[nod];
if(ai2[nod*2]!=bignumber)
ai2[nod*2]+=lazy[nod];
if(ai2[nod*2+1]!=bignumber)
ai2[nod*2+1]+=lazy[nod];
if(ai3[nod*2]!=-bignumber)
ai3[nod*2]+=lazy[nod];
if(ai3[nod*2+1]!=-bignumber)
ai3[nod*2+1]+=lazy[nod];
if(ai4[nod*2]!=-bignumber)
ai4[nod*2]+=lazy[nod];
if(ai4[nod*2+1]!=-bignumber)
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]!=bignumber)
ai1[nod]+=val;
if(ai2[nod]!=bignumber)
ai2[nod]+=val;
if(ai3[nod]!=-bignumber)
ai3[nod]+=val;
if(ai4[nod]!=-bignumber)
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={bignumber,-bignumber},rez2={bignumber,-bignumber};
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]=bignumber;
ai3[nod]=-bignumber;
}
else if(val%2==1)
{
ai2[nod]=ai3[nod]=val;
ai1[nod]=bignumber;
ai4[nod]=-bignumber;
}
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("in","r",stdin);
//freopen("out","w",stdout);
cin.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==bignumber)
{
cout<<-1<<' ';
}
else
{
cout<<rez.first<<' ';
}
if(rez.second==-bignumber)
{
cout<<-1<<'\n';
}
else
{
cout<<rez.second<<'\n';
}
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
896 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
137 ms |
13560 KB |
Output is correct |
| 2 |
Correct |
299 ms |
26872 KB |
Output is correct |
| 3 |
Correct |
286 ms |
26916 KB |
Output is correct |
| 4 |
Correct |
300 ms |
27000 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
896 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
