#include <iostream>
using namespace std;
struct sus
{
int maxpar=-1,minpar=-1,maximpar=-1,minimpar=-1,lazy=0;
}aint[400005];
int v[200005];
sus join(sus a, sus b)
{
sus x;
x.lazy=0;
if(a.maxpar==-1)
{
x.maxpar=b.maxpar;
x.minpar=b.minpar;
}
else if(b.maxpar==-1)
{
x.maxpar=a.maxpar;
x.minpar=a.minpar;
}
else
x.maxpar=max(a.maxpar,b.maxpar),x.minpar=min(a.minpar,b.minpar);
if(a.maximpar==-1)
{
x.maximpar=b.maximpar;
x.minimpar=b.minimpar;
}
else if(b.maximpar==-1)
{
x.maximpar=a.maximpar;
x.minimpar=a.minimpar;
}
else
x.maximpar=max(a.maximpar,b.maximpar),x.minimpar=min(a.minimpar,b.minimpar);
return x;
}
pair<int,int>join2(pair<int,int>a, pair<int,int>b)
{
if(a.first==-1)
return {b.first, max(a.second,b.second)};
if(b.first==-1)
return {a.first, max(a.second,b.second)};
return {min(a.first,b.first), max(a.second,b.second)};
}
void build(int poz, int st, int dr)
{
if(st==dr)
{
if(v[st]%2==0)
aint[poz].maxpar=v[st],aint[poz].minimpar=-1,aint[poz].minpar=v[st],aint[poz].maximpar=-1;
else
aint[poz].maximpar=v[st],aint[poz].minpar=-1,aint[poz].minimpar=v[st],aint[poz].maxpar=-1;
return;
}
int mid=(st+dr)/2;
build(2*poz,st,mid);
build(2*poz+1,mid+1,dr);
}
void propag(int poz, int st, int dr, int x)
{
if(x%2==0)
{
if(aint[poz].maxpar!=-1)
aint[poz].maxpar+=x;
if(aint[poz].minpar!=-1)
aint[poz].minpar+=x;
if(aint[poz].maximpar!=-1)
aint[poz].maximpar+=x;
if(aint[poz].minimpar!=-1)
aint[poz].minimpar+=x;
}
else
{
sus a=aint[poz];
if(a.maxpar!=-1)
aint[poz].maximpar+=x;
if(a.minpar!=-1)
aint[poz].minimpar+=x;
if(a.maximpar!=-1)
aint[poz].maxpar+=x;
if(a.minimpar!=-1)
aint[poz].minpar+=x;
}
if(st!=dr)
{
aint[2*poz].lazy+=x;
aint[2*poz+1].lazy+=x;
}
aint[poz].lazy=0;
return;
}
void update(int poz, int st, int dr, int a, int b, int c)
{
propag(poz, st, dr, aint[poz].lazy);
if(a<=st && dr<=b)
{
propag(poz,st,dr,c);
return;
}
int mid=(st+dr)/2;
if(mid>=a)
update(2*poz,st,mid,a,b,c);
if(mid+1<=b)
update(2*poz+1,mid+1,dr,a,b,c);
aint[poz]=join(aint[2*poz],aint[2*poz+1]);
}
pair<int,int> query(int poz,int st, int dr, int a, int b)
{
propag(poz, st, dr, aint[poz].lazy);
if(a<=st && dr<=b)
return {aint[poz].minpar,aint[poz].maximpar};
int mid=(st+dr)/2;
if(b<=mid)
return query(2*poz,st,mid,a,b);
if(mid+1<=a)
return query(2*poz+1,mid+1,dr,a,b);
return join2(query(2*poz,st,mid,a,b),query(2*poz+1,mid+1,dr,a,b));
}
int main()
{
int n,q;
cin>>n;
for(int i=1;i<=n;i++)
cin>>v[i];
build(1,1,n);
cin>>q;
for(int i=0;i<q;i++)
{
int tip,a,b,c;
cin>>tip>>a>>b;
if(tip==0)
{
cin>>c;
update(1,1,n,a,b,c);
}
else
{
pair<int,int>u=query(1,1,n,a,b);
cout<<u.first<<" "<<u.second<<'\n';
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
357 ms |
7140 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
