#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmax(a, b) a = max(a, b)
#define chkmin(a, b) a = min(a, b)
#define int ll
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll, ll> pii;
typedef vector<pii> vii;
const int block = 800;
const int MAX_N = 3e5 + 5;
int nx[MAX_N][2];
pii dp[MAX_N][2];
pii dq[MAX_N];
int rangesl[MAX_N / block + 1][block];
int rangesr[MAX_N / block + 1][block];
int ran[MAX_N][2];
int sz[MAX_N / block + 1];
void Update(int a, int b) {
int dl = MAX_N / 2, dr = MAX_N / 2;
for (int i = a; i < b; i++) {
while (dl < dr) {
if (ran[dq[dl].x][dq[dl].y] < ran[i][0]) {
nx[dq[dl].x][dq[dl].y] = i;
dl++;
} else if (ran[dq[dr - 1].x][dq[dr - 1].y] > ran[i][1]) {
nx[dq[dr - 1].x][dq[dr - 1].y] = i;
dr--;
} else break;
}
dq[--dl] = {i, 0}, dq[dr++] = {i, 1};
}
while (dl < dr) {
nx[dq[dl].x][dq[dl].y] = b;
dl++;
}
for (int i = b - 1; i >= a; i--) {
for (int j = 0; j < 2; j++) {
int x = nx[i][j];
if (x == b) {
dp[i][j] = {0, ran[i][j]};
} else {
if (ran[i][j] > ran[x][1]) {
dp[i][j] = {dp[x][1].x + ran[i][j] - ran[x][1], dp[x][1].y};
} else {
dp[i][j] = {dp[x][0].x, dp[x][0].y};
}
}
}
}
int bl = a / block;
sz[bl] = b - a;
rangesl[bl][0] = ran[a][0];
rangesr[bl][0] = ran[a][1];
for (int i = a + 1; i < b; i++) {
rangesl[bl][i - a] = max(rangesl[bl][i - a - 1], ran[i][0]);
rangesr[bl][i - a] = min(rangesr[bl][i - a - 1], ran[i][1]);
}
}
ll Query(int a, int b, int c, int d) {
ll ans = 0;
while (a < c && a % block) {
if (b < ran[a][0]) b = ran[a][0];
else if (b > ran[a][1]) ans += b - ran[a][1], b = ran[a][1];
a++;
}
while (a + block < c) {
int bl = a / block;
int i = min(lower_bound(rangesl[bl], rangesl[bl] + sz[bl], b) - rangesl[bl],
lower_bound(rangesr[bl], rangesr[bl] + sz[bl], b, greater<int>()) - rangesr[bl]) + a;
if (i < a + block) {
if (b <= ran[i][0]) {
ans += dp[i][0].x;
b = dp[i][0].y;
} else if (b >= ran[i][1]) {
ans += dp[i][1].x;
ans += b - ran[i][1];
b = dp[i][1].y;
}
}
a += block;
}
while (a < c) {
if (b < ran[a][0]) b = ran[a][0];
else if (b > ran[a][1]) ans += b - ran[a][1], b = ran[a][1];
a++;
}
return ans + max<ll>(0, b - d);
}
int L[MAX_N], R[MAX_N], t[MAX_N], a[MAX_N], b[MAX_N], c[MAX_N], d[MAX_N];
ll ans[MAX_N];
int32_t main() {
int n, q;
cin >> n >> q;
for (int i = 0; i + 1 < n; i++) cin >> L[i] >> R[i];
for (int i = 0; i < q; i++) {
cin >> t[i] >> a[i] >> b[i] >> c[i];
if (t[i] == 2) cin >> d[i];
}
for (int i = 0; i < q; i++) a[i]--, c[i]--;
for (int i = 0; i + 1 < n; i++) R[i]--;
for (int ti = 0; ti < 2; ti++) {
for (int i = 0; i + 1 < n; i++) {
ran[i][0] = L[i] - i, ran[i][1] = R[i] - i;
}
for (int i = 0; i < n; i += block) {
Update(i, min(i + block, n - 1));
}
for (int i = 0; i < q; i++) {
if (t[i] == 1) {
ran[a[i]][0] = b[i] - a[i], ran[a[i]][1] = c[i] - a[i];
Update(a[i] / block * block, min(n - 1, a[i] / block * (block + 1)));
} else {
// if (a[i] < c[i] || (a[i] == c[i] && !ti)) {
// b[i] -= a[i], d[i] -= c[i];
// while (a[i] < c[i]) {
// if (b[i] < ran[a[i]][0]) b[i] = ran[a[i]][0];
// else if (b[i] > ran[a[i]][1]) ans[i] += b[i] - ran[a[i]][1], b[i] = ran[a[i]][1];
// a[i]++;
// }
// ans[i] += max<ll>(0, b[i] - d[i]);
// }
if (a[i] <= c[i]) ans[i] = Query(a[i], b[i] - a[i], c[i], d[i] - c[i]);
}
}
reverse(L, L + n - 1), reverse(R, R + n - 1);
for (int i = 0; i < q; i++) {
if (t[i] == 1) a[i] = n - 2 - a[i];
else a[i] = n - 1 - a[i], c[i] = n - 1 - c[i];
}
}
for (int i = 0; i < q; i++) {
if (t[i] == 2) cout << ans[i] << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
26960 KB |
Output is correct |
| 2 |
Correct |
3 ms |
26960 KB |
Output is correct |
| 3 |
Correct |
3 ms |
26960 KB |
Output is correct |
| 4 |
Correct |
4 ms |
26960 KB |
Output is correct |
| 5 |
Correct |
4 ms |
27036 KB |
Output is correct |
| 6 |
Correct |
3 ms |
26960 KB |
Output is correct |
| 7 |
Correct |
4 ms |
26960 KB |
Output is correct |
| 8 |
Correct |
4 ms |
26960 KB |
Output is correct |
| 9 |
Correct |
3 ms |
26960 KB |
Output is correct |
| 10 |
Correct |
3 ms |
27092 KB |
Output is correct |
| 11 |
Correct |
6 ms |
26960 KB |
Output is correct |
| 12 |
Incorrect |
5 ms |
26960 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2904 ms |
51096 KB |
Output is correct |
| 2 |
Correct |
2511 ms |
66096 KB |
Output is correct |
| 3 |
Correct |
2591 ms |
66220 KB |
Output is correct |
| 4 |
Correct |
2548 ms |
66028 KB |
Output is correct |
| 5 |
Correct |
2806 ms |
66648 KB |
Output is correct |
| 6 |
Correct |
2665 ms |
66484 KB |
Output is correct |
| 7 |
Correct |
2384 ms |
66596 KB |
Output is correct |
| 8 |
Correct |
2504 ms |
67624 KB |
Output is correct |
| 9 |
Correct |
2368 ms |
66336 KB |
Output is correct |
| 10 |
Correct |
2611 ms |
66764 KB |
Output is correct |
| 11 |
Correct |
2693 ms |
66676 KB |
Output is correct |
| 12 |
Correct |
2886 ms |
67436 KB |
Output is correct |
| 13 |
Correct |
2791 ms |
67604 KB |
Output is correct |
| 14 |
Correct |
2 ms |
14672 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
26960 KB |
Output is correct |
| 2 |
Correct |
3 ms |
26960 KB |
Output is correct |
| 3 |
Correct |
3 ms |
26960 KB |
Output is correct |
| 4 |
Correct |
4 ms |
26960 KB |
Output is correct |
| 5 |
Correct |
4 ms |
27036 KB |
Output is correct |
| 6 |
Correct |
3 ms |
26960 KB |
Output is correct |
| 7 |
Correct |
4 ms |
26960 KB |
Output is correct |
| 8 |
Correct |
4 ms |
26960 KB |
Output is correct |
| 9 |
Correct |
3 ms |
26960 KB |
Output is correct |
| 10 |
Correct |
3 ms |
27092 KB |
Output is correct |
| 11 |
Correct |
6 ms |
26960 KB |
Output is correct |
| 12 |
Incorrect |
5 ms |
26960 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
