#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <algorithm>
#include <cstring>
#include <cassert>
using namespace std;
#define FOR(i, a, b) for (int i = a; i < (int) b; i++)
#define F0R(i, a) FOR(i, 0, a)
#define ROF(i, a, b) for (int i = a; i >= (int) b; i--)
#define R0F(i, a) ROF(i, a, 0)
#define GO(i, a) for (auto i : a)
#define f first
#define s second
#define eb emplace_back
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef vector<vi> vvi;
typedef vector<vpii> vvpii;
typedef long long i64;
typedef vector<i64> vi64;
const int dr[] = {+1, -1, +0, +0, +1, -1, +1, -1};
const int dc[] = {+0, +0, +1, -1, +1, -1, -1, +1};
const int ms[] = {+31, +29, +31, 30, +31, +30, +31, +31, +30, +31, +30, +31};
void setIO(string nome) {
ios_base::sync_with_stdio(0); cin.tie(0);
freopen ((nome + ".in").c_str(), "r", stdin);
freopen ((nome + ".out").c_str(), "w", stdout);
}
const int N = 2e5 + 5;
int a [N];
struct Node {
i64 mx_odd, mn_odd;
i64 mx_even, mn_even;
i64 lazy;
Node () {
mx_odd = mx_even = -1;
mn_even = mn_odd = 1e17;
lazy = 0;
}
void merge (Node l, Node r) {
mx_odd = max (l.mx_odd, r.mx_odd);
mx_even = max (l.mx_even, r.mx_even);
mn_even = min (l.mn_even, r.mn_even);
mn_odd = min (l.mn_odd, r.mn_odd);
}
};
struct SegmentTree {
vector<Node> seg;
SegmentTree (int n) {
seg.clear();
seg.resize(4 * n);
build (0, n - 1, 0);
}
void build (int l, int r, int node) {
if (l == r) {
if (a[l] & 1) {
seg[node].mx_odd = seg[node].mn_odd = a[l];
} else {
seg[node].mx_even = seg[node].mn_even = a[l];
}
} else {
int mid = l + (r - l) / 2;
build (l, mid, 2 * node + 1);
build (mid + 1, r, 2 * node + 2);
seg[node].merge(seg[2 * node + 1], seg[2 * node + 2]);
}
}
void pushdown (int l, int r, int node) {
if (seg[node].mx_even != -1) {
seg[node].mx_even += seg[node].lazy;
}
if (seg[node].mx_odd != -1) {
seg[node].mx_odd += seg[node].lazy;
}
if (seg[node].mn_even < 1e16) {
seg[node].mn_even += seg[node].lazy;
}
if (seg[node].mn_odd < 1e16) {
seg[node].mn_odd += seg[node].lazy;
}
if (l != r) {
seg[2 * node + 1].lazy += seg[node].lazy;
seg[2 * node + 2].lazy += seg[node].lazy;
}
if (seg[node].lazy & 1) {
swap (seg[node].mx_even, seg[node].mx_odd);
swap (seg[node].mn_even, seg[node].mn_odd);
}
seg[node].lazy = 0;
}
void update (int ql, int qr, int delta, int l, int r, int node) {
if (seg[node].lazy > 0) pushdown (l, r, node);
if (l > qr || r < ql) return;
if (l >= ql && r <= qr) {
if (seg[node].mx_even != -1) {
seg[node].mx_even += delta;
}
if (seg[node].mx_odd != -1) {
seg[node].mx_odd += delta;
}
if (seg[node].mn_even < 1e16) {
seg[node].mn_even += delta;
}
if (seg[node].mn_odd < 1e16) {
seg[node].mn_odd += delta;
}
if (l != r) {
seg[2 * node + 1].lazy += delta;
seg[2 * node + 2].lazy += delta;
}
if (delta & 1) {
swap (seg[node].mx_even, seg[node].mx_odd);
swap (seg[node].mn_even, seg[node].mn_odd);
}
return;
}
int mid = l + (r - l) / 2;
update (ql, qr, delta, l, mid, 2 * node + 1);
update (ql, qr, delta, mid + 1, r, 2 * node + 2);
seg[node].merge(seg[2 * node + 1], seg[2 * node + 2]);
}
i64 query_odd (int ql, int qr, int l, int r, int node) {
if (seg[node].lazy > 0) pushdown (l, r, node);
if (l > qr || r < ql) return -1;
if (l >= ql && r <= qr) return seg[node].mx_odd;
int mid = l + (r - l) / 2;
return max (query_odd (ql, qr, l, mid, 2 * node + 1), query_odd (ql, qr, mid + 1, r, 2 * node + 2));
}
i64 query_even (int ql, int qr, int l, int r, int node) {
if (seg[node].lazy > 0) pushdown (l, r, node);
if (l > qr || r < ql) return 1e18;
if (l >= ql && r <= qr) return seg[node].mn_even;
int mid = l + (r - l) / 2;
return min (query_even (ql, qr, l, mid, 2 * node + 1), query_even (ql, qr, mid + 1, r, 2 * node + 2));
}
};
int main () {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
F0R (i, n) cin >> a[i];
SegmentTree seg (n);
int q;
cin >> q;
while (q--) {
int task, lo, hi;
cin >> task >> lo >> hi;
--lo; --hi;
if (task == 1) {
i64 q_even = seg.query_even (lo, hi, 0, n - 1, 0);
if (q_even > 1e16) q_even = -1;
i64 q_odd = seg.query_odd (lo, hi, 0, n - 1, 0);
cout << q_even << ' ' << q_odd << '\n';
} else {
int delta;
cin >> delta;
seg.update (lo, hi, delta, 0, n - 1, 0);
}
}
return 0;
}
Compilation message
subway.cpp: In function 'void setIO(std::__cxx11::string)':
subway.cpp:38:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen ((nome + ".in").c_str(), "r", stdin);
~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
subway.cpp:39:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen ((nome + ".out").c_str(), "w", stdout);
~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
1144 KB |
Output is correct |
| 2 |
Correct |
12 ms |
1144 KB |
Output is correct |
| 3 |
Correct |
13 ms |
1400 KB |
Output is correct |
| 4 |
Correct |
13 ms |
1400 KB |
Output is correct |
| 5 |
Correct |
13 ms |
1400 KB |
Output is correct |
| 6 |
Correct |
13 ms |
1400 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
194 ms |
20564 KB |
Output is correct |
| 2 |
Correct |
412 ms |
40984 KB |
Output is correct |
| 3 |
Correct |
417 ms |
41080 KB |
Output is correct |
| 4 |
Correct |
416 ms |
40996 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
1144 KB |
Output is correct |
| 2 |
Correct |
12 ms |
1144 KB |
Output is correct |
| 3 |
Correct |
13 ms |
1400 KB |
Output is correct |
| 4 |
Correct |
13 ms |
1400 KB |
Output is correct |
| 5 |
Correct |
13 ms |
1400 KB |
Output is correct |
| 6 |
Correct |
13 ms |
1400 KB |
Output is correct |
| 7 |
Correct |
194 ms |
20564 KB |
Output is correct |
| 8 |
Correct |
412 ms |
40984 KB |
Output is correct |
| 9 |
Correct |
417 ms |
41080 KB |
Output is correct |
| 10 |
Correct |
416 ms |
40996 KB |
Output is correct |
| 11 |
Correct |
236 ms |
21112 KB |
Output is correct |
| 12 |
Correct |
576 ms |
41528 KB |
Output is correct |
| 13 |
Correct |
507 ms |
42296 KB |
Output is correct |
| 14 |
Correct |
543 ms |
41464 KB |
Output is correct |
| 15 |
Correct |
493 ms |
42704 KB |
Output is correct |
| 16 |
Correct |
139 ms |
39032 KB |
Output is correct |
