#include <bits/stdc++.h>
#define mp make_pair
using namespace std;
typedef long long ll;
struct tcio {
bool t;
ll c;
int i, o;
} mx[1048576], mx2[1048576], ab;
tcio merge(tcio a1, tcio a2) {
if (a1.t == 0) {
if (a2.t == 0) {
if (a1.i > a2.o) return {1, (ll) a1.i - a2.o, a1.i, a2.o};
if (a1.o < a2.i) return {1, 0ll, a1.o, a2.i};
return {0, 0ll, max(a1.i, a2.i), min(a1.o, a2.o)};
}
if (a2.i < a1.i) return {1, (ll) a1.i - a2.i + a2.c, a1.i, a2.o};
if (a2.i > a1.o) return {1, a2.c, a1.o, a2.o};
}
if (a2.t == 0) {
if (a1.o < a2.i) return {1, a1.c, a1.i, a2.i};
if (a1.o > a2.o) return {1, (ll) a1.o - a2.o + a1.c, a1.i, a2.o};
return {1, a1.c, a1.i, a1.o};
}
return {1, max((ll) a1.o - a2.i, 0ll) + a1.c + a2.c, a1.i, a2.o};
}
void upd(pair<int, int> v, int id, int n, int ql, int qr) {
if (id < ql || id > qr) {
return;
}
if (ql == qr) {
mx[n] = {0, 0, v.first, v.second};
return;
}
int m = (ql + qr) / 2;
upd(v, id, n * 2, ql, m);
upd(v, id, n * 2 + 1, m + 1, qr);
mx[n] = merge(mx[n * 2], mx[n * 2 + 1]);
return;
}
void upd2(pair<int, int> v, int id, int n, int ql, int qr) {
if (id < ql || id > qr) {
return;
}
if (ql == qr) {
mx2[n] = {0, 0, v.first, v.second};
return;
}
int m = (ql + qr) / 2;
upd2(v, id, n * 2, ql, m);
upd2(v, id, n * 2 + 1, m + 1, qr);
mx2[n] = merge(mx2[n * 2], mx2[n * 2 + 1]);
return;
}
tcio qry(int l, int r, int n, int ql, int qr) {
if (l > qr || r < ql) {
return {0, 0, -1000000001, 1000000001};
}
if (ql >= l && qr <= r) {
return mx[n];
}
int m = (ql + qr) / 2;
return merge(qry(l, r, n * 2, ql, m), qry(l, r, n * 2 + 1, m + 1, qr));
}
tcio qry2(int l, int r, int n, int ql, int qr) {
if (l > qr || r < ql) {
return {0, 0, -1000000001, 1000000001};
}
if (ql >= l && qr <= r) {
return mx2[n];
}
int m = (ql + qr) / 2;
return merge(qry2(l, r, n * 2, ql, m), qry2(l, r, n * 2 + 1, m + 1, qr));
}
int main(){
int n, q, j, la, ra, t, p, s, e, ca, ta, cb, tb;
cin >> n >> q;
n--;
for (int i = 0; i < n; i++) {
cin >> la >> ra;
ra--;
mx[i + 524288].i = la - i;
mx[i + 524288].o = ra - i;
j = n - i - 1;
mx2[j + 524288].i = la - j;
mx2[j + 524288].o = ra - j;
}
for (int i = n + 524288; i < 1048576; i++) {
mx[i].i = -1000000001;
mx[i].o = 1000000001;
mx2[i].i = -1000000001;
mx2[i].o = 1000000001;
}
for (int i = 524287; i > 0; i--) {
mx[i] = merge(mx[i * 2], mx[i * 2 + 1]);
mx2[i] = merge(mx2[i * 2], mx2[i * 2 + 1]);
}
for (int i = 0; i < q; i++) {
cin >> t;
if (t == 1) {
cin >> p >> s >> e;
p--, e--, j = n - p - 1;
upd(mp(s - p, e - p), p, 1, 0, 524287);
upd2(mp(s - j, e - j), j, 1, 0, 524287);
} else {
cin >> ca >> ta >> cb >> tb;
ca--, cb--, tb--;
if (ca <= cb) {
cb--, ta -= ca, tb -= cb;
ab = merge(merge({0, 0, ta, ta}, qry(ca, cb, 1, 0, 524287)), {0, 0, tb, tb});
} else {
ca = n - ca, cb = n - cb, cb--, ta -= ca, tb -= cb;
ab = merge(merge({0, 0, ta, ta}, qry2(ca, cb, 1, 0, 524287)), {0, 0, tb, tb});
}
cout << ab.c << '\n';
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
41 ms |
49484 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1821 ms |
53772 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
41 ms |
49484 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
