#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,a[200005],q;
int inf = 1000000000000000000ll;
struct aint_nod
{
int lazy = 0,maxpar = -inf,maximp = -inf,minpar = inf,minimp = inf;
};
aint_nod aint[800005];
void build(int p,int l,int r)
{
if (l == r)
{
if (a[l] % 2 == 1)
aint[p].maximp = a[l],aint[p].minimp = a[l];
else
aint[p].maxpar = a[l],aint[p].minpar = a[l];
}
else
{
int mij = (l + r) / 2;
int fs = 2 * p,fd = 2 * p + 1;
build(fs,l,mij);
build(fd,mij + 1,r);
aint[p].maxpar = max(aint[fs].maxpar,aint[fd].maxpar);
aint[p].maximp = max(aint[fs].maximp,aint[fd].maximp);
aint[p].minpar = min(aint[fs].minpar,aint[fd].minpar);
aint[p].minimp = min(aint[fs].minimp,aint[fd].minimp);
}
}
void prop_lazy(int p,int l,int r)
{
if (aint[p].lazy % 2 == 0)
{
aint[p].maxpar += aint[p].lazy;
aint[p].maximp += aint[p].lazy;
aint[p].minpar += aint[p].lazy;
aint[p].minimp += aint[p].lazy;
}
else
{
swap(aint[p].maxpar,aint[p].maximp);
swap(aint[p].minpar,aint[p].minimp);
aint[p].maxpar += aint[p].lazy;
aint[p].maximp += aint[p].lazy;
aint[p].minpar += aint[p].lazy;
aint[p].minimp += aint[p].lazy;
}
if (l != r)
{
int fs = 2 * p,fd = 2 * p + 1;
aint[fs].lazy += aint[p].lazy;
aint[fd].lazy += aint[p].lazy;
}
aint[p].lazy = 0;
}
void update(int p,int l,int r,int st,int dr,int val)
{
prop_lazy(p,l,r);
if (st <= l and r <= dr)
{
aint[p].lazy += val;
prop_lazy(p,l,r);
return;
}
int fs = 2 * p,fd = 2 * p + 1,mij = (l + r) / 2;
if (mij >= st)
update(fs,l,mij,st,dr,val);
if (mij + 1 <= dr)
update(fd,mij + 1,r,st,dr,val);
aint[p].maxpar = max(aint[fs].maxpar,aint[fd].maxpar);
aint[p].maximp = max(aint[fs].maximp,aint[fd].maximp);
aint[p].minpar = min(aint[fs].minpar,aint[fd].minpar);
aint[p].minimp = min(aint[fs].minimp,aint[fd].minimp);
}
pair<int,int>better(pair<int,int>p1,pair<int,int>p2)
{
if (p1.first == -1 and p1.second == -1)
return p2;
if (p2.first == -1 and p2.second == -1)
return p1;
pair<int,int>ans;
ans.first = min(p1.first,p2.first);
ans.second = max(p1.second,p2.second);
return ans;
}
pair<int,int>query(int p,int l,int r,int st,int dr)
{
prop_lazy(p,l,r);
if (st <= l and r <= dr)
return {aint[p].minpar,aint[p].maximp};
int fs = 2 * p,fd = 2 * p + 1,mij = (l + r) / 2;
pair<int,int>p1 = {-1,-1},p2 = {-1,-1};
if (mij >= st)
p1 = query(fs,l,mij,st,dr);
if (mij + 1 <= dr)
p2 = query(fd,mij + 1,r,st,dr);
return better(p1,p2);
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
build(1,1,n);
cin >> q;
for (int i = 1; i <= q; i++)
{
int tip;
cin >> tip;
if (tip == 0)
{
int x,y,val;
cin >> x >> y >> val;
update(1,1,n,x,y,val);
}
else
{
int x,y;
cin >> x >> y;
pair<int,int>qr = query(1,1,n,x,y);
if (qr.second >= inf / 10 or qr.second <= -inf / 10)
qr.second = -1;
if (qr.first <= -inf / 10 or qr.first >= inf / 10)
qr.first = -1;
cout << qr.first << ' ' << qr.second << '\n';
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
31700 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
122 ms |
36464 KB |
Output is correct |
| 2 |
Correct |
254 ms |
41672 KB |
Output is correct |
| 3 |
Correct |
257 ms |
41600 KB |
Output is correct |
| 4 |
Correct |
285 ms |
41676 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
31700 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
