oj.uz

답안 #1115432

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1115432 2024-11-20T13:02:34 Z elush Bitaro, who Leaps through Time (JOI19_timeleap) C++14
30 / 100
 2904 ms 67624 KB 
#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';
    }
}

Subtask #1
0 / 4.0

# 결과 실행 시간 메모리 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 -

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 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

Subtask #3
0 / 66.0

# 결과 실행 시간 메모리 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 -