#include <bits/stdc++.h>
using namespace std;
#define int long long
struct node
{
int pmin, pmax, imin, imax, lazy;
node()
{
pmin = pmax = imin = imax = -1;
lazy = 0;
}
void operator = (vector<int>v)
{
pmin = v[0], pmax = v[1], imin = v[2], imax = v[3], lazy = v[4];
}
};
node operator + (node a, node b)
{
node ans;
if (a.pmin == -1)
ans.pmin = b.pmin;
else if (b.pmin == -1)
ans.pmin = a.pmin;
else
ans.pmin = min(a.pmin, b.pmin);
if (a.pmax == -1)
ans.pmax = b.pmax;
else if (b.pmax == -1)
ans.pmax = a.pmax;
else
ans.pmax = max(a.pmax, b.pmax);
if (a.imin == -1)
ans.imin = b.imin;
else if (b.imin == -1)
ans.imin = a.imin;
else
ans.imin = min(a.imin, b.imin);
if (a.imax == -1)
ans.imax = b.imax;
else if (b.imax == -1)
ans.imax = a.imax;
else
ans.imax = max(a.imax, b.imax);
return ans;
}
class ST
{
protected:
int n;
vector<node>a;
public:
void init (int N)
{
n = 1;
while (n < N)
n <<= 1;
n <<= 1;
n++;
a.resize(n);
}
void propagate (int nod, int st, int dr)
{
if (a[nod].lazy)
{
int lazy = a[nod].lazy;
if (lazy % 2 == 0)
{
if (a[nod].pmin != -1)
{
a[nod].pmin += lazy;
a[nod].pmax += lazy;
}
if (a[nod].imin != -1)
{
a[nod].imin += lazy;
a[nod].imax += lazy;
}
}
else
{
int pmin = a[nod].pmin, pmax = a[nod].pmax;
int imin = a[nod].imin, imax = a[nod].imax;
if (pmin != -1)
{
a[nod].imin = pmin + lazy;
a[nod].imax = pmax + lazy;
}
else
a[nod].imin = a[nod].imax = -1;
if (imin != -1)
{
a[nod].pmin = imin + lazy;
a[nod].pmax = imax + lazy;
}
else
a[nod].pmin = a[nod].pmax = -1;
}
if (st != dr)
{
a[2*nod].lazy += a[nod].lazy;
a[2*nod+1].lazy += a[nod].lazy;
}
a[nod].lazy = 0;
}
}
void build (int nod, int st, int dr)
{
if (st == dr)
{
int x;
cin >> x;
if (x % 2 == 0)
a[nod] = {x, x, -1, -1, 0};
else
a[nod] = {-1, -1, x, x, 0};
}
else
{
int mid = (st + dr) / 2;
build(2*nod, st, mid);
build(2*nod+1, mid+1, dr);
a[nod] = a[2*nod] + a[2*nod+1];
}
}
void update (int nod, int st, int dr, int l, int r, int x)
{
propagate(nod, st, dr);
if (l <= st && dr <= r)
a[nod].lazy += x;
else
{
int mid = (st + dr) / 2;
if (l <= mid)
update(2*nod, st, mid, l, r, x);
if (mid < r)
update(2*nod+1, mid+1, dr, l, r, x);
propagate(2*nod, st, mid);
propagate(2*nod+1, mid+1, dr);
a[nod] = a[2*nod] + a[2*nod+1];
}
}
node query (int nod, int st, int dr, int l, int r)
{
propagate(nod, st, dr);
if (l <= st && dr <= r)
return a[nod];
int mid = (st + dr) / 2;
if (l <= mid && mid < r)
{
node ls = query(2*nod, st, mid, l, r);
node rs = query(2*nod+1, mid+1, dr, l, r);
return ls + rs;
}
if (l <= mid)
{
return query(2*nod, st, mid, l, r);
}
if (mid < r)
{
return query(2*nod+1, mid+1, dr, l, r);
}
}
};
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
ST a;
a.init(n);
a.build(1, 1, n);
int q;
cin >> q;
while (q--)
{
int op;
cin >> op;
if (op == 0)
{
int x, y, val;
cin >> x >> y >> val;
a.update(1, 1, n, x, y, val);
}
else
{
//cout << a[2].pmin << ' ' << a[3].pmin << ' ' << a[4].pmin << '\n';
int x, y;
cin >> x >> y;
node ans = a.query(1, 1, n, x, y);
cout << ans.pmin << ' ' << ans.imax << '\n';
}
}
return 0;
}
Compilation message
subway.cpp: In member function 'node ST::query(long long int, long long int, long long int, long long int, long long int)':
subway.cpp:194:5: warning: control reaches end of non-void function [-Wreturn-type]
194 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
596 KB |
Output is correct |
| 2 |
Correct |
8 ms |
724 KB |
Output is correct |
| 3 |
Correct |
7 ms |
1108 KB |
Output is correct |
| 4 |
Correct |
7 ms |
1108 KB |
Output is correct |
| 5 |
Correct |
7 ms |
1172 KB |
Output is correct |
| 6 |
Correct |
6 ms |
1084 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
121 ms |
12276 KB |
Output is correct |
| 2 |
Correct |
264 ms |
24256 KB |
Output is correct |
| 3 |
Correct |
269 ms |
24328 KB |
Output is correct |
| 4 |
Correct |
239 ms |
24284 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
596 KB |
Output is correct |
| 2 |
Correct |
8 ms |
724 KB |
Output is correct |
| 3 |
Correct |
7 ms |
1108 KB |
Output is correct |
| 4 |
Correct |
7 ms |
1108 KB |
Output is correct |
| 5 |
Correct |
7 ms |
1172 KB |
Output is correct |
| 6 |
Correct |
6 ms |
1084 KB |
Output is correct |
| 7 |
Correct |
121 ms |
12276 KB |
Output is correct |
| 8 |
Correct |
264 ms |
24256 KB |
Output is correct |
| 9 |
Correct |
269 ms |
24328 KB |
Output is correct |
| 10 |
Correct |
239 ms |
24284 KB |
Output is correct |
| 11 |
Correct |
204 ms |
15152 KB |
Output is correct |
| 12 |
Correct |
370 ms |
29780 KB |
Output is correct |
| 13 |
Correct |
326 ms |
30540 KB |
Output is correct |
| 14 |
Correct |
392 ms |
29720 KB |
Output is correct |
| 15 |
Correct |
291 ms |
31108 KB |
Output is correct |
| 16 |
Correct |
103 ms |
27340 KB |
Output is correct |
