/*
simple : given a array of n elements and q queries(type 0, add a to every element in range [x, y],
type 1, find the max odd number and the min even number from range [x, y]), answer to the queries of type 1)
Classical lazy propagation task
*/
#include<bits/stdc++.h>
using namespace std;
int n, q;
long long v[200002], aint[5][800002], lazy[800002];
long long Minpar, Maximpar;
void build(int nod, int st, int dr)
{
if(st == dr)
{
aint[0][nod] = aint[2][nod] = (1LL<<60);
aint[1][nod] = aint[3][nod] = -(1LL<<60);
if(v[st] % 2 == 0)
aint[0][nod] = aint[1][nod] = v[st];
else
aint[2][nod] = aint[3][nod] = v[st];
return;
}
int mid = (st + dr) / 2;
build(nod << 1, st, mid);
build(nod << 1|1, mid + 1, dr);
long long minpar = (1LL<<60);
if(aint[0][2 * nod] != (1LL<<60))
minpar = min(minpar, aint[0][nod * 2]);
if(aint[0][2 * nod + 1] != (1LL<<60))
minpar = min(minpar, aint[0][nod * 2 + 1]);
aint[0][nod] = minpar;
long long maxpar = -(1LL<<60);
if(aint[1][2 * nod] != -(1LL<<60))
maxpar = max(maxpar, aint[1][nod * 2]);
if(aint[1][2 * nod + 1] != -(1LL<<60))
maxpar = max(maxpar, aint[1][nod * 2 + 1]);
aint[1][nod] = maxpar;
minpar = (1LL<<60);
if(aint[2][2 * nod] != (1LL<<60))
minpar = min(minpar, aint[2][nod * 2]);
if(aint[2][2 * nod + 1] != (1LL<<60))
minpar = min(minpar, aint[2][nod * 2 + 1]);
aint[2][nod] = minpar;
maxpar = -(1LL<<60);
if(aint[3][2 * nod] != -(1LL<<60))
maxpar = max(maxpar, aint[3][nod * 2]);
if(aint[3][2 * nod + 1] != -(1LL<<60))
maxpar = max(maxpar, aint[3][nod * 2 + 1]);
aint[3][nod] = maxpar;
}
void update(int nod, int st, int dr, int l, int r, int val)
{
if(l <= st && dr <= r)
lazy[nod] += val;
if(lazy[nod])
{
if(aint[0][nod] != (1LL<<60))
aint[0][nod] += lazy[nod], aint[1][nod] += lazy[nod];
if(aint[2][nod] != (1LL<<60))
aint[2][nod] += lazy[nod], aint[3][nod] += lazy[nod];
if(lazy[nod] % 2 == 1)
{
swap(aint[0][nod], aint[2][nod]);
swap(aint[1][nod], aint[3][nod]);
}
if(st != dr)
{
lazy[2 * nod] += lazy[nod];
lazy[2 * nod + 1] += lazy[nod];
}
lazy[nod] = 0;
}
if(dr < l || st > r)
return;
if(l <= st && dr <= r)
return;
int mid = (st + dr) / 2;
update(nod * 2, st, mid, l, r, val);
update(nod * 2 + 1, mid + 1, dr, l, r, val);
long long minpar = (1LL<<60);
if(aint[0][2 * nod] != (1LL<<60))
minpar = min(minpar, aint[0][nod * 2]);
if(aint[0][2 * nod + 1] != (1LL<<60))
minpar = min(minpar, aint[0][nod * 2 + 1]);
aint[0][nod] = minpar;
long long maxpar = -(1LL<<60);
if(aint[1][2 * nod] != -(1LL<<60))
maxpar = max(maxpar, aint[1][nod * 2]);
if(aint[1][2 * nod + 1] != -(1LL<<60))
maxpar = max(maxpar, aint[1][nod * 2 + 1]);
aint[1][nod] = maxpar;
minpar = (1LL<<60);
if(aint[2][2 * nod] != (1LL<<60))
minpar = min(minpar, aint[2][nod * 2]);
if(aint[2][2 * nod + 1] != (1LL<<60))
minpar = min(minpar, aint[2][nod * 2 + 1]);
aint[2][nod] = minpar;
maxpar = -(1LL<<60);
if(aint[3][2 * nod] != -(1LL<<60))
maxpar = max(maxpar, aint[3][nod * 2]);
if(aint[3][2 * nod + 1] != -(1LL<<60))
maxpar = max(maxpar, aint[3][nod * 2 + 1]);
aint[3][nod] = maxpar;
}
void query(int nod, int st, int dr, int l, int r)
{
if(lazy[nod])
{
if(aint[0][nod] != (1LL<<60))
aint[0][nod] += lazy[nod], aint[1][nod] += lazy[nod];
if(aint[2][nod] != (1LL<<60))
aint[2][nod] += lazy[nod], aint[3][nod] += lazy[nod];
if(lazy[nod] % 2 == 1)
{
swap(aint[0][nod], aint[2][nod]);
swap(aint[1][nod], aint[3][nod]);
}
if(st != dr)
{
lazy[2 * nod] += lazy[nod];
lazy[2 * nod + 1] += lazy[nod];
}
lazy[nod] = 0;
}
if(dr < l || st > r)
return;
if(l <= st && dr <= r)
{
if(aint[0][nod])
Minpar = min(Minpar, aint[0][nod] + lazy[nod]);
if(aint[3][nod])
Maximpar = max(Maximpar, aint[3][nod] + lazy[nod]);
return;
}
int mid = (st + dr) / 2;
query(nod * 2, st, mid, l, r);
query(nod * 2 + 1, mid + 1, dr, l, r);
long long minpar = (1LL<<60);
if(aint[0][2 * nod] != (1LL<<60))
minpar = min(minpar, aint[0][nod * 2]);
if(aint[0][2 * nod + 1] != (1LL<<60))
minpar = min(minpar, aint[0][nod * 2 + 1]);
aint[0][nod] = minpar;
long long maxpar = -(1LL<<60);
if(aint[1][2 * nod] != -(1LL<<60))
maxpar = max(maxpar, aint[1][nod * 2]);
if(aint[1][2 * nod + 1] != -(1LL<<60))
maxpar = max(maxpar, aint[1][nod * 2 + 1]);
aint[1][nod] = maxpar;
minpar = (1LL<<60);
if(aint[2][2 * nod] != (1LL<<60))
minpar = min(minpar, aint[2][nod * 2]);
if(aint[2][2 * nod + 1] != (1LL<<60))
minpar = min(minpar, aint[2][nod * 2 + 1]);
aint[2][nod] = minpar;
maxpar = -(1LL<<60);
if(aint[3][2 * nod] != -(1LL<<60))
maxpar = max(maxpar, aint[3][nod * 2]);
if(aint[3][2 * nod + 1] != -(1LL<<60))
maxpar = max(maxpar, aint[3][nod * 2 + 1]);
aint[3][nod] = maxpar;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
for(int i = 1; i <= n; ++i)
cin >> v[i];
build(1, 1, n);
cin >> q;
for(int i = 1; i <= q; ++i)
{
int tip;
cin >> tip;
if(tip == 0)
{
int a, b, val;
cin >> a >> b >> val;
update(1, 1, n, a, b, val);
}
else
{
int a, b;
cin >> a >> b;
Maximpar = -(1LL<<60);
Minpar = (1LL<<60);
query(1, 1, n, a, b);
if(Minpar == (1LL<<60))
cout << -1 << " ";
else
cout << Minpar << " ";
if(Maximpar == -(1LL<<60))
cout << -1 << '\n';
else
cout << Maximpar << '\n';
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
8792 KB |
Output is correct |
| 2 |
Correct |
5 ms |
8796 KB |
Output is correct |
| 3 |
Correct |
6 ms |
10752 KB |
Output is correct |
| 4 |
Correct |
6 ms |
10844 KB |
Output is correct |
| 5 |
Correct |
7 ms |
10844 KB |
Output is correct |
| 6 |
Correct |
6 ms |
10844 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
97 ms |
20448 KB |
Output is correct |
| 2 |
Correct |
232 ms |
35096 KB |
Output is correct |
| 3 |
Correct |
260 ms |
35176 KB |
Output is correct |
| 4 |
Correct |
247 ms |
35024 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
8792 KB |
Output is correct |
| 2 |
Correct |
5 ms |
8796 KB |
Output is correct |
| 3 |
Correct |
6 ms |
10752 KB |
Output is correct |
| 4 |
Correct |
6 ms |
10844 KB |
Output is correct |
| 5 |
Correct |
7 ms |
10844 KB |
Output is correct |
| 6 |
Correct |
6 ms |
10844 KB |
Output is correct |
| 7 |
Correct |
97 ms |
20448 KB |
Output is correct |
| 8 |
Correct |
232 ms |
35096 KB |
Output is correct |
| 9 |
Correct |
260 ms |
35176 KB |
Output is correct |
| 10 |
Correct |
247 ms |
35024 KB |
Output is correct |
| 11 |
Correct |
126 ms |
24144 KB |
Output is correct |
| 12 |
Correct |
333 ms |
39692 KB |
Output is correct |
| 13 |
Correct |
290 ms |
40352 KB |
Output is correct |
| 14 |
Correct |
296 ms |
39676 KB |
Output is correct |
| 15 |
Correct |
254 ms |
40916 KB |
Output is correct |
| 16 |
Correct |
65 ms |
32852 KB |
Output is correct |
