oj.uz

답안 #1115404

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1115404 2024-11-20T12:38:23 Z elush Bitaro, who Leaps through Time (JOI19_timeleap) C++14
4 / 100
 3000 ms 42752 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 = 650;
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 = 1000, dr = 1000;
    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][0]);
    }
}

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 < 1; ti++) {
        for (int i = 0; i + 1 < n; i++) {
            ran[i][0] = L[i], ran[i][1] = R[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));
        }
        for (int i = 0; i < q; i++) {
            if (t[i] == 1) {
                ran[a[i]][0] = b[i], ran[a[i]][1] = c[i];
//                ran[a[i]][0] = b[i] - a[i], ran[a[i]][1] = c[i] - a[i];
                Update(a[i] / block * block, min(n, 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]++, b[i]++;
                    }
                    while (a[i] > c[i]) {
                        a[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];
                        b[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++) {
            a[i] = n - 1 - a[i];
            if (t[i] == 2) c[i] = n - 1 - c[i];
        }
    }
    for (int i = 0; i < q; i++) {
        if (t[i] == 2) cout << ans[i] << '\n';
    }

//    for (int i = 0; i < n; i++) l[i] = L[i], r[i] = R[i];
//    for (int i = 0; i < q; i++) {
//        if (t[i] == 1) {
//            l[a[i]] = b[i], r[a[i]] = c[i];
//            continue;
//        }
//        if (a[i] <= c[i]) {
//            ll ti = b[i], ans = 0;
//            for (int j = a[i]; j < c[i]; j++) {
//                if (ti < l[j]) ti = l[j];
//                else if (ti > r[j]) ans += ti - r[j], ti = r[j];
//                ti++;
//            }
//            ans += max<ll>(0, ti - d[i]);
//            cout << ans << '\n';
//        } else {
//            ll ti = b[i], ans = 0;
//            for (int j = a[i] - 1; j >= c[i]; j--) {
//                if (ti < l[j]) ti = l[j];
//                else if (ti >= r[j]) ans += ti - r[j], ti = r[j];
//                ti++;
//            }
//            ans += max<ll>(0, ti - d[i]);
//            cout << ans << '\n';
//        }
//    }

}

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 26960 KB Output is correct
2 Correct 3 ms 27092 KB Output is correct
3 Correct 3 ms 27076 KB Output is correct
4 Correct 3 ms 26960 KB Output is correct
5 Correct 4 ms 26960 KB Output is correct
6 Correct 3 ms 26960 KB Output is correct
7 Correct 3 ms 27120 KB Output is correct
8 Correct 3 ms 26960 KB Output is correct
9 Correct 3 ms 26960 KB Output is correct
10 Correct 3 ms 27096 KB Output is correct
11 Correct 6 ms 26960 KB Output is correct
12 Correct 6 ms 26960 KB Output is correct
13 Correct 5 ms 26960 KB Output is correct
14 Correct 5 ms 26960 KB Output is correct
15 Correct 6 ms 26960 KB Output is correct
16 Correct 5 ms 26960 KB Output is correct
17 Correct 7 ms 27128 KB Output is correct
18 Correct 5 ms 26960 KB Output is correct
19 Correct 5 ms 26960 KB Output is correct
20 Correct 5 ms 27160 KB Output is correct
21 Correct 5 ms 26960 KB Output is correct
22 Correct 4 ms 26960 KB Output is correct
23 Correct 5 ms 27132 KB Output is correct
24 Correct 6 ms 27144 KB Output is correct
25 Correct 5 ms 27268 KB Output is correct
26 Correct 5 ms 26960 KB Output is correct
27 Correct 5 ms 26960 KB Output is correct
28 Correct 5 ms 26960 KB Output is correct
29 Correct 5 ms 26960 KB Output is correct
30 Correct 5 ms 26960 KB Output is correct
31 Correct 5 ms 26960 KB Output is correct
32 Correct 5 ms 26960 KB Output is correct
33 Correct 5 ms 26960 KB Output is correct
34 Correct 5 ms 27120 KB Output is correct
35 Correct 5 ms 26960 KB Output is correct
36 Correct 6 ms 26960 KB Output is correct
37 Correct 5 ms 26960 KB Output is correct
38 Correct 6 ms 27132 KB Output is correct
39 Correct 5 ms 26960 KB Output is correct
40 Correct 5 ms 26960 KB Output is correct
41 Correct 3 ms 20828 KB Output is correct

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3067 ms 42752 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 66.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 26960 KB Output is correct
2 Correct 3 ms 27092 KB Output is correct
3 Correct 3 ms 27076 KB Output is correct
4 Correct 3 ms 26960 KB Output is correct
5 Correct 4 ms 26960 KB Output is correct
6 Correct 3 ms 26960 KB Output is correct
7 Correct 3 ms 27120 KB Output is correct
8 Correct 3 ms 26960 KB Output is correct
9 Correct 3 ms 26960 KB Output is correct
10 Correct 3 ms 27096 KB Output is correct
11 Correct 6 ms 26960 KB Output is correct
12 Correct 6 ms 26960 KB Output is correct
13 Correct 5 ms 26960 KB Output is correct
14 Correct 5 ms 26960 KB Output is correct
15 Correct 6 ms 26960 KB Output is correct
16 Correct 5 ms 26960 KB Output is correct
17 Correct 7 ms 27128 KB Output is correct
18 Correct 5 ms 26960 KB Output is correct
19 Correct 5 ms 26960 KB Output is correct
20 Correct 5 ms 27160 KB Output is correct
21 Correct 5 ms 26960 KB Output is correct
22 Correct 4 ms 26960 KB Output is correct
23 Correct 5 ms 27132 KB Output is correct
24 Correct 6 ms 27144 KB Output is correct
25 Correct 5 ms 27268 KB Output is correct
26 Correct 5 ms 26960 KB Output is correct
27 Correct 5 ms 26960 KB Output is correct
28 Correct 5 ms 26960 KB Output is correct
29 Correct 5 ms 26960 KB Output is correct
30 Correct 5 ms 26960 KB Output is correct
31 Correct 5 ms 26960 KB Output is correct
32 Correct 5 ms 26960 KB Output is correct
33 Correct 5 ms 26960 KB Output is correct
34 Correct 5 ms 27120 KB Output is correct
35 Correct 5 ms 26960 KB Output is correct
36 Correct 6 ms 26960 KB Output is correct
37 Correct 5 ms 26960 KB Output is correct
38 Correct 6 ms 27132 KB Output is correct
39 Correct 5 ms 26960 KB Output is correct
40 Correct 5 ms 26960 KB Output is correct
41 Correct 3 ms 20828 KB Output is correct
42 Execution timed out 3067 ms 42752 KB Time limit exceeded
43 Halted 0 ms 0 KB -