#include <iostream>
#define int long long
#define inf 1000000000000000000
using namespace std;
int n,q,val,tip,a,b,v[200010],lazy[3600010];
struct {int pmin,pmax,imin,imax;}aint[3600010];
void build(int poz,int l,int r)
{
aint[poz].pmin=inf;
aint[poz].imin=inf+1;
aint[poz].pmax=-inf;
aint[poz].imax=-inf-1;
if(l==r)
{
if(v[l]%2==0)
{
aint[poz].pmax=v[l];
aint[poz].pmin=v[l];
}
else
{
aint[poz].imax=v[l];
aint[poz].imin=v[l];
}
return;
}
if(l>r)
return;
int m=(l+r)/2;
build(poz*2,l,m);
build(poz*2+1,m+1,r);
aint[poz].pmax=max(aint[poz*2].pmax,aint[poz*2+1].pmax);
aint[poz].imax=max(aint[poz*2].imax,aint[poz*2+1].imax);
aint[poz].imin=min(aint[poz*2].imin,aint[poz*2+1].imin);
aint[poz].pmin=min(aint[poz*2].pmin,aint[poz*2+1].pmin);
return;
}
void update(int poz,int l,int r,int a,int b,int val)
{
if(r<a||l>b)
{
aint[poz].imax+=lazy[poz];
aint[poz].pmax+=lazy[poz];
aint[poz].pmin+=lazy[poz];
aint[poz].imin+=lazy[poz];
if(aint[poz].imin%2==0)
{
swap(aint[poz].imin,aint[poz].pmin);
swap(aint[poz].imax,aint[poz].pmax);
}
if(l<r)
{
lazy[poz*2]+=lazy[poz];
lazy[poz*2+1]+=lazy[poz];
}
lazy[poz]=0;
return;
}
if(a<=l&&r<=b)
{
aint[poz].imax+=val+lazy[poz];
aint[poz].pmax+=val+lazy[poz];
aint[poz].pmin+=val+lazy[poz];
aint[poz].imin+=val+lazy[poz];
if(aint[poz].imin%2==0)
{
swap(aint[poz].imin,aint[poz].pmin);
swap(aint[poz].imax,aint[poz].pmax);
}
if(l<r)
{
lazy[poz*2]+=lazy[poz]+val;
lazy[poz*2+1]+=lazy[poz]+val;
}
lazy[poz]=0;
return;
}
lazy[poz*2]+=lazy[poz];
lazy[poz*2+1]+=lazy[poz];
lazy[poz]=0;
int m=(l+r)/2;
update(poz*2,l,m,a,b,val);
update(poz*2+1,m+1,r,a,b,val);
aint[poz].pmax=max(aint[poz*2].pmax,aint[poz*2+1].pmax);
aint[poz].imax=max(aint[poz*2].imax,aint[poz*2+1].imax);
aint[poz].imin=min(aint[poz*2].imin,aint[poz*2+1].imin);
aint[poz].pmin=min(aint[poz*2].pmin,aint[poz*2+1].pmin);
return;
}
void raspuns(int poz,int l,int r,int a,int b,int &minpar,int &maximpar)
{
if(r<a||l>b)
{
aint[poz].imax+=lazy[poz];
aint[poz].pmax+=lazy[poz];
aint[poz].pmin+=lazy[poz];
aint[poz].imin+=lazy[poz];
if(aint[poz].imin%2==0)
{
swap(aint[poz].imin,aint[poz].pmin);
swap(aint[poz].imax,aint[poz].pmax);
}
if(l<r)
{
lazy[poz*2]+=lazy[poz];
lazy[poz*2+1]+=lazy[poz];
}
lazy[poz]=0;
return;
}
if(a<=l&&r<=b)
{
aint[poz].imax+=lazy[poz];
aint[poz].pmax+=lazy[poz];
aint[poz].pmin+=lazy[poz];
aint[poz].imin+=lazy[poz];
if(aint[poz].imin%2==0)
{
swap(aint[poz].imin,aint[poz].pmin);
swap(aint[poz].imax,aint[poz].pmax);
}
if(l<r)
{
lazy[poz*2]+=lazy[poz];
lazy[poz*2+1]+=lazy[poz];
}
lazy[poz]=0;
maximpar=max(maximpar,aint[poz].imax);
minpar=min(minpar,aint[poz].pmin);
return;
}
lazy[poz*2]+=lazy[poz];
lazy[poz*2+1]+=lazy[poz];
lazy[poz]=0;
int m=(l+r)/2;
raspuns(poz*2,l,m,a,b,minpar,maximpar);
raspuns(poz*2+1,m+1,r,a,b,minpar,maximpar);
aint[poz].pmax=max(aint[poz*2].pmax,aint[poz*2+1].pmax);
aint[poz].imax=max(aint[poz*2].imax,aint[poz*2+1].imax);
aint[poz].imin=min(aint[poz*2].imin,aint[poz*2+1].imin);
aint[poz].pmin=min(aint[poz*2].pmin,aint[poz*2+1].pmin);
return;
}
main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>n;
for(int i=1;i<=n;++i)
cin>>v[i];
build(1,1,n);
cin>>q;
while(q--)
{
cin>>tip>>a>>b;
if(tip==0)
{
cin>>val;
update(1,1,n,a,b,val);
}
else
{
int minpar=inf,maximpar=-inf;
raspuns(1,1,n,a,b,minpar,maximpar);
if(minpar>400000000000000)
cout<<-1<<' ';
else
cout<<minpar<<' ';
if(maximpar<0)
cout<<-1<<'\n';
else
cout<<maximpar<<'\n';
}
}
return 0;
}
Compilation message
subway.cpp:144:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
144 | main()
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
712 KB |
Output is correct |
| 2 |
Correct |
5 ms |
708 KB |
Output is correct |
| 3 |
Correct |
6 ms |
1096 KB |
Output is correct |
| 4 |
Correct |
5 ms |
1208 KB |
Output is correct |
| 5 |
Correct |
5 ms |
1228 KB |
Output is correct |
| 6 |
Correct |
6 ms |
1224 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
134 ms |
15464 KB |
Output is correct |
| 2 |
Correct |
299 ms |
30884 KB |
Output is correct |
| 3 |
Correct |
297 ms |
30872 KB |
Output is correct |
| 4 |
Correct |
311 ms |
30900 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
712 KB |
Output is correct |
| 2 |
Correct |
5 ms |
708 KB |
Output is correct |
| 3 |
Correct |
6 ms |
1096 KB |
Output is correct |
| 4 |
Correct |
5 ms |
1208 KB |
Output is correct |
| 5 |
Correct |
5 ms |
1228 KB |
Output is correct |
| 6 |
Correct |
6 ms |
1224 KB |
Output is correct |
| 7 |
Correct |
134 ms |
15464 KB |
Output is correct |
| 8 |
Correct |
299 ms |
30884 KB |
Output is correct |
| 9 |
Correct |
297 ms |
30872 KB |
Output is correct |
| 10 |
Correct |
311 ms |
30900 KB |
Output is correct |
| 11 |
Correct |
142 ms |
16000 KB |
Output is correct |
| 12 |
Correct |
314 ms |
31292 KB |
Output is correct |
| 13 |
Correct |
355 ms |
32032 KB |
Output is correct |
| 14 |
Correct |
344 ms |
31264 KB |
Output is correct |
| 15 |
Correct |
316 ms |
32636 KB |
Output is correct |
| 16 |
Correct |
92 ms |
24644 KB |
Output is correct |
