#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define forn(i,n) for(int i=0;i<n;i++)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(),v.rend()
#define pb push_back
#define sz(a) (int)a.size()
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
struct T{
int min_par, min_impar, max_impar, max_par;
};
T merge(T x, T y){
int MN_PAR = -1, MXPAR = -1, MNIMPAR =-1,MXIMPAR=-1;
if(x.min_par != -1)MN_PAR = x.min_par;
if(y.min_par != -1)MN_PAR = y.min_par;
if(x.min_par != -1)MN_PAR = min(MN_PAR, x.min_par);
if(y.min_par != -1)MN_PAR = min(MN_PAR, y.min_par);
if(x.max_par != -1)MXPAR = x.max_par;
if(y.max_par != -1)MXPAR = y.max_par;
if(x.max_par != -1)MXPAR = max(MXPAR, x.max_par);
if(y.max_par != -1)MXPAR = max(MXPAR, y.max_par);
if(x.max_impar != -1)MXIMPAR = x.max_impar;
if(y.max_impar != -1)MXIMPAR = y.max_impar;
if(x.max_impar != -1)MXIMPAR = max(MXIMPAR, x.max_impar);
if(y.max_impar != -1)MXIMPAR = max(MXIMPAR, y.max_impar);
if(x.min_impar != -1)MNIMPAR = x.min_impar;
if(y.min_impar != -1)MNIMPAR = y.min_impar;
if(x.min_impar != -1)MNIMPAR = min(MNIMPAR, x.min_impar);
if(y.min_impar != -1)MNIMPAR = min(MNIMPAR, y.min_impar);
return {MN_PAR,MNIMPAR,MXIMPAR,MXPAR};
}
const int maxn = 1e6;
T tree[maxn];
int lazy[maxn];
void push(int i, int l, int r)
{
if(lazy[i] == 0)return;
if(tree[i].min_par !=-1)tree[i].min_par += lazy[i];
if(tree[i].min_impar != -1)tree[i].min_impar+=lazy[i];
if(tree[i].max_par != -1)tree[i].max_par += lazy[i];
if(tree[i].max_impar != -1)tree[i].max_impar +=lazy[i];
if(lazy[i]&1)
{
swap(tree[i].min_par, tree[i].min_impar);
swap(tree[i].max_par,tree[i].max_impar);
}
if(l != r){
lazy[2 * i] += lazy[i];
lazy[2 * i + 1] += lazy[i];
}
lazy[i] = 0;
}
void modif(int i, int l, int r, int tl, int tr, int val)
{
if(l > tr || r < tl)return;
if(l >= tl && r <= tr){
lazy[i] +=val;
push(i,l,r);
return;
}
push(i,l,r);
int mid = (l + r) >> 1;
modif(2 * i, l, mid, tl, tr, val);
modif(2 * i + 1,mid + 1, r, tl, tr, val);
tree[i] = merge(tree[2 * i], tree[2 * i + 1]);
}
T query(int i, int l, int r, int tl, int tr)
{
push(i,l,r);
if(l > tr || r < tl)return {-1,-1,-1, -1};
if(l >= tl && r<=tr)return tree[i];
int mid = (l + r) >> 1;
T left = query(2 * i, l, mid, tl,tr);
T right = query(2 * i + 1, mid + 1, r, tl,tr);
return merge(left,right);
}
int a[maxn];
void build(int i, int l, int r)
{
if(l==r)
{
if(a[l]%2==0)
{
tree[i].min_par = a[l];
tree[i].max_par = a[l];
tree[i].min_impar = -1;
tree[i].max_impar = -1;
}
if(a[l]&1)
{
tree[i].min_par = -1;
tree[i].max_par = -1;
tree[i].max_impar = a[l];
tree[i].min_impar = a[l];
}
return;
}
int mid = (l + r) >> 1;
build(2 * i, l,mid);
build(2 * i + 1, mid + 1, r);
tree[i] = merge(tree[2 * i], tree[2 * i + 1]);
}
void solve()
{
int n, q;
cin >> n;
forn(i,n){
cin >> a[i];
}
build(1,0,n-1);
cin >> q;
while(q--)
{
int type;
cin >> type;
if(type==0)
{
int l,r,x;
cin >> l >> r >> x;
--l,--r;
modif(1,0,n-1,l,r,x);
}
if(type == 1)
{
int l,r;
cin >> l >> r;
--l,--r;
T ans = query(1,0,n-1,l,r);
cout << ans.min_par << " " << ans.max_impar << '\n';
}
}
}
int32_t main()
{
fastio;
int t = 1;
//cin >> t;
while(t--)
{
solve();
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
199 ms |
11116 KB |
Output is correct |
| 2 |
Correct |
427 ms |
21996 KB |
Output is correct |
| 3 |
Correct |
445 ms |
21868 KB |
Output is correct |
| 4 |
Correct |
443 ms |
21868 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
