#include <bits/stdc++.h>
#define fr first
#define sc second
#define ll long long
using namespace std;
const int N = (int)3e5 + 7;
int n, q;
pair<int, int> ar[N];
struct node {
ll l, r, cost, to;
node() {
l = -1e18;
r = 1e18;
cost = -1;
to = 0;
}
node(ll _l, ll _r, ll _cost, ll _to) {
l = _l;
r = _r;
cost = _cost;
to = _to;
}
};
node merge(node a, node b) {
if (a.cost != -1) {
a.cost += max(a.to - b.r, 0LL);
a.to = max(b.l, min(a.to, b.r));
if (b.cost != -1) {
a.to = b.to;
a.cost += b.cost;
}
} else if (a.l > b.r) {
a = {a.l, a.l, a.l - b.r, b.r};
if (b.cost != -1) {
a.to = b.to;
a.cost += b.cost;
}
} else if (a.r < b.l) {
a = {a.r, a.r, 0, b.l};
if (b.cost != -1) {
a.to = b.to;
a.cost += b.cost;
}
} else if (b.cost != -1) {
a = b;
} else {
a.l = max(a.l, b.l);
a.r = min(a.r, b.r);
}
return a;
}
node tree[N * 4];
void upd(int pos, node val, int v = 1, int l = 1, int r = n) {
if (l == r) {
tree[v] = val;
return ;
}
int mid = (l + r) >> 1;
if (pos <= mid) {
upd(pos, val, v + v, l, mid);
} else {
upd(pos, val, v + v + 1, mid + 1, r);
}
tree[v] = merge(tree[v + v], tree[v + v + 1]);
}
node get(int l, int r, int v = 1, int tl = 1, int tr = n) {
if (tl > r || tr < l) return node();
if (l <= tl && tr <= r) return tree[v];
int mid = (tl + tr) >> 1;
return merge(get(l, r, v + v, tl, mid), get(l, r, v + v + 1, mid + 1, tr));
}
int A[N], B[N], C[N], D[N], tp[N];
ll ans[N];
main() {
scanf("%d %d", &n, &q);
for (int i = 1; i < n; i++) {
scanf("%d %d", &ar[i].fr, &ar[i].sc);
upd(i, node(ar[i].fr - i, ar[i].sc - i - 1, -1, 0));
}
for (int i = 1; i <= q; i++) {
scanf("%d", &tp[i]);
if (tp[i] == 1) {
scanf("%d %d %d", &A[i], &B[i], &C[i]);
upd(A[i], node(B[i] - A[i], C[i] - A[i] - 1, -1, 0));
} else {
scanf("%d %d %d %d", &A[i], &B[i], &C[i], &D[i]);
if (A[i] > C[i]) continue;
B[i] -= A[i];
D[i] -= C[i];
if (A[i] == C[i]) {
ans[i] = max(B[i] - D[i], 0);
B[i] += A[i];
D[i] += C[i];
continue;
}
//node asd = get(A[i], C[i] - 1);
//cout << asd.l << ' ' << asd.r << ' ' << asd.cost << ' ' << asd.to << '\n';
ans[i] = merge(node(B[i], B[i], 0, B[i]), merge(get(A[i], C[i] - 1), node(D[i], D[i], 0, D[i]))).cost;
B[i] += A[i];
D[i] += C[i];
}
}
for (int i = 1; i < n; i++) {
upd(n - i, node(ar[i].fr + i + 1, ar[i].sc + i, -1, 0));
}
for (int i = n - 1; i >= 1; i--) {
cout << ar[i].fr + i + 1 << ' ' << ar[i].sc + i << '\n';
}
for (int i = 1; i <= q; i++) {
if (tp[i] == 1) {
upd(n - A[i], node(B[i] + A[i] + 1, C[i] + A[i], -1, 0));
} else {
if (A[i] <= C[i]) continue;
B[i] += A[i];
D[i] += C[i];
//node asd = get(n - A[i] + 1, n - C[i]);
//cout << asd.l << ' ' << asd.r << ' ' << asd.cost << ' ' << asd.to << '\n';
ans[i] = merge(node(B[i], B[i], 0, B[i]), merge(get(n - A[i] + 1, n - C[i]), node(D[i], D[i], 0, D[i]))).cost;
}
}
for (int i = 1; i <= q; i++) {
if (tp[i] == 2) {
printf("%lld\n", ans[i]);
}
}
}
Compilation message
timeleap.cpp:84:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main() {
^
timeleap.cpp: In function 'int main()':
timeleap.cpp:85:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &n, &q);
~~~~~^~~~~~~~~~~~~~~~~
timeleap.cpp:87:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &ar[i].fr, &ar[i].sc);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
timeleap.cpp:91:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &tp[i]);
~~~~~^~~~~~~~~~~~~~
timeleap.cpp:93:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &A[i], &B[i], &C[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
timeleap.cpp:96:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d %d", &A[i], &B[i], &C[i], &D[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
31 ms |
38016 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1113 ms |
73356 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
31 ms |
38016 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
