| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1033384 | thangdz2k7 | Bitaro, who Leaps through Time (JOI19_timeleap) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3e5 + 5;
const long long inf = -1e18;
struct Node{
long long val[2][2];
Node(){
for (int i = 0; i < 2; ++ i)
for (int j = 0; j < 2; ++ j) val[i][j] = inf;
val[0][0] = 0;
}
};
Node mer(Node a, Node b){
Node c;
for (int i = 0; i < 2; ++ i){
for (int j = 0; j < 2; ++ j) c.val[i][j] = max(a.val[i][j], b.val[i][j]);
}
for (int i = 0; i < 2; ++ i){
for (int l = 0; l < 2; ++ l){
for (int j = 0; j < 2; ++ j) c.val[i][j] = max(c.val[i][j], a.val[i][l] + b.val[l][j]);
}
}
return c;
}
struct Segtree{
Node it[4 * N];
void update(int s, int l, int r, int u, int i, int j){
//if (i == j && i == 3 && u == 3) cout << l << ' ' << r << ' ' << u << endl;
if (l == r){
it[s].val[0][0] = 0;
it[s].val[1][0] = l - j;
it[s].val[0][1] = i - l;
return;
}
int mid = l + r >> 1;
if (mid >= u) update(2 * s, l, mid, u, i, j);
else update(2 * s + 1, mid + 1, r, u, i, j);
it[s] = mer(it[2 * s], it[2 * s + 1]);
}
Node get(int s, int l, int r, int u, int v){
if (u <= l && r <= v) return it[s];
int mid = l + r >> 1;
Node a, b;
int bl = 0, br = 0;
if (mid >= u) a = get(2 * s, l, mid, u, v), bl = 1;
if (mid + 1 <= v) b = get(2 * s + 1, mid + 1, r, u, v), br = 1;
if (!bl) return b;
if (!br) return a;
return mer(a, b);
}
} seg1, seg2;
int in[N], out[N], n, q;
void solve(){
cin >> n >> q;
for (int i = 1; i <= n - 1; ++ i){
cin >> in[i] >> out[i];
seg1.update(1, 0, n, i, in[i], out[i] - 1);
seg2.update(1, 0, n, n - i, in[i], out[i] - 1);
}
while (q --){
int t; cin >> t;
if (t & 1){
int i; cin >> i;
cin >> in[i] >> out[i];
seg1.update(1, 0, n, i, in[i], out[i] - 1);
seg2.update(1, 0, n, n - i, in[i], out[i] - 1);
}
else {
int s, ts, e, te;
cin >> s >> ts >> e >> te;
if (s <= e){
seg1.update(1, 0, n, s - 1, ts - 1, ts - 1);
seg1.update(1, 0, n, e, te, te);
//cout << t << ' ' << s << ' ' << ts << ' ' << e << ' ' << te endl;
//cout << it[7].val[1][0] << endl;
cout << seg1.get(1, 0, n, s - 1, e).val[0][0] << '\n';
seg1.update(1, 0, n, s - 1, in[s - 1], out[s - 1] - 1);
seg1.update(1, 0, n, e, in[e], out[e] - 1);
}
else {
swap(s, e);
seg2.update(1, 0, n, n - e, ts - 1, ts - 1);
seg2.update(1, 0, n, n - s + 1, te, te);
//cout << n - e << ' ' << ts - 1 << ' ' << ts - 1 << endl;
//for (int i = n - e + 1; i < n - s + 1; ++ i) cout << i << ' ' << in[n - i] << ' ' << out[n - i] - 1 << endl;
//cout << n - s + 1 << ' ' << te << ' ' << te << endl;
cout << seg2.get(1, 0, n, n - e - 1, n + 1 - s).val[0][0] << '\n';
seg2.update(1, 0, n, n - e, in[e], out[e] - 1);
seg2.update(1, 0, n, n + 1 - s, in[s - 1], out[s - 1] - 1);
}
}
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
solve();
return 0;
}