#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const long long MAXN = 2e5 + 10;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
long long n, a[MAXN];
void read_array()
{
cin >> n;
for (long long i = 1; i <= n; ++ i)
{
cin >> a[i];
}
}
struct node
{
long long mineven, maxeven, minodd, maxodd;
node(){};
node(long long _mineven, long long _maxeven, long long _minodd, long long _maxodd)
{
mineven = _mineven;
maxeven = _maxeven;
minodd = _minodd;
maxodd = _maxodd;
}
};
node t[4 * MAXN];
long long lazy[4 * MAXN];
void make_tree(long long i, long long l, long long r)
{
if(l == r)
{
if(a[l] & 1)
{
t[i].maxodd = a[l];
t[i].minodd = a[l];
t[i].maxeven = -1;
t[i].mineven = 1e17;
}
else
{
t[i].maxeven = a[l];
t[i].mineven = a[l];
t[i].maxodd = -1;
t[i].minodd = 1e17;
}
return;
}
long long mid = (l + r)/2;
make_tree(2*i, l, mid);
make_tree(2*i+1, mid+1, r);
t[i].maxodd = max(t[2*i].maxodd, t[2*i+1].maxodd);
t[i].minodd = min(t[2*i].minodd, t[2*i+1].minodd);
t[i].maxeven = max(t[2*i].maxeven, t[2*i+1].maxeven);
t[i].mineven = min(t[2*i].mineven, t[2*i+1].mineven);
}
void push_lazy(long long i, long long l, long long r)
{
t[i].maxodd = t[i].maxodd + lazy[i];
t[i].minodd = t[i].minodd + lazy[i];
t[i].maxeven = t[i].maxeven + lazy[i];
t[i].mineven = t[i].mineven + lazy[i];
if(lazy[i] & 1)
{
swap(t[i].maxodd, t[i].maxeven);
swap(t[i].minodd, t[i].mineven);
}
if(l != r)
{
lazy[2*i] += lazy[i];
lazy[2*i+1] += lazy[i];
}
lazy[i] = 0;
}
long long ql, qr;
pair < long long/**minimum even*/, long long/**maxodd*/> query(long long i, long long l, long long r)
{
// cout << i << " " << l << " " << r << endl;
push_lazy(i, l, r);
if(qr < l || ql > r)return make_pair(1e17, -1);
if(ql <= l && r <= qr)
{
return make_pair(t[i].mineven, t[i].maxodd);
}
long long mid = (l + r)/2;
pair < long long , long long > first_half = query(2*i, l, mid);
pair < long long, long long > second_half = query(2*i+1, mid+1, r);
pair < long long, long long > ans = make_pair(min(first_half.first, second_half.first), max(first_half.second, second_half.second));
return ans;
}
long long val;
void update(long long i, long long l, long long r)
{
push_lazy(i, l, r);
if(qr < l || ql > r)return;
if(ql <= l && r <= qr)
{
lazy[i] += val;
push_lazy(i, l, r);
return;
}
int mid = (l + r)/2;
update(2*i, l, mid);
update(2*i+1, mid+1, r);
t[i].maxodd = max(t[2*i].maxodd, t[2*i+1].maxodd);
t[i].minodd = min(t[2*i].minodd, t[2*i+1].minodd);
t[i].maxeven = max(t[2*i].maxeven, t[2*i+1].maxeven);
t[i].mineven = min(t[2*i].mineven, t[2*i+1].mineven);
}
int main()
{
speed();
read_array();
make_tree(1, 1, n);
long long q;
cin >> q;
long long type;
while(q --)
{
cin >> type;
if(type == 1)
{
cin >> ql >> qr;
pair < long long, long long > qq = query(1, 1, n);
if(qq.first == 1e17 || qq.first & 1)cout << -1 << " ";
else cout << qq.first << " ";
if(qq.second == -1 || !(qq.second & 1))cout << -1 << endl;
else cout << qq.second << endl;
//cout << .first << " " << query(1, 1, n).second << endl;
}
else
{
cin >> ql >> qr >> val;
update(1, 1, n);
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
724 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
163 ms |
13192 KB |
Output is correct |
| 2 |
Correct |
275 ms |
25936 KB |
Output is correct |
| 3 |
Correct |
282 ms |
25892 KB |
Output is correct |
| 4 |
Correct |
265 ms |
25836 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
724 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
