oj.uz

Submission #1115416

# Submission time Handle Problem Language Result Execution time Memory
1115416 2024-11-20T12:48:35 Z elush Bitaro, who Leaps through Time (JOI19_timeleap) C++14
0 / 100
 2973 ms 49048 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 = 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 < 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));
        }
        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, 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

# Verdict Execution time Memory Grader output
1 Correct 3 ms 26960 KB Output is correct
2 Correct 4 ms 27044 KB Output is correct
3 Correct 3 ms 26960 KB Output is correct
4 Correct 3 ms 26960 KB Output is correct
5 Correct 3 ms 26960 KB Output is correct
6 Correct 3 ms 26960 KB Output is correct
7 Correct 3 ms 26968 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 26960 KB Output is correct
11 Correct 5 ms 27008 KB Output is correct
12 Incorrect 5 ms 26960 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 2973 ms 49048 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 26960 KB Output is correct
2 Correct 4 ms 27044 KB Output is correct
3 Correct 3 ms 26960 KB Output is correct
4 Correct 3 ms 26960 KB Output is correct
5 Correct 3 ms 26960 KB Output is correct
6 Correct 3 ms 26960 KB Output is correct
7 Correct 3 ms 26968 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 26960 KB Output is correct
11 Correct 5 ms 27008 KB Output is correct
12 Incorrect 5 ms 26960 KB Output isn't correct
13 Halted 0 ms 0 KB -