Submission #1062864

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062864		TheQuantiX	Dungeons Game (IOI21_dungeons)	C++17	50 / 100	7077 ms	1531988 KiB

dungeons

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

ll n, m, q, k, x, y, a, b, c;
vector<int> s, p, w, l;
vector<__int128> wup[40];
vector<__int128> wupmx[40];
vector<__int128> wupm[40];
vector<__int128> lup[40];
vector<__int128> lupmn[40];
vector<__int128> lupm[40];

void init(int N, vector<int> S, vector<int> P, vector<int> W, vector<int> L) {
    n = N;
    s = S;
    p = P;
    w = W;
    l = L;
    for (int i = 0; i < 40; i++) {
        wup[i].resize(n + 1);
        wupmx[i].resize(n + 1);
        wupm[i].resize(n + 1);
        lup[i].resize(n + 1);
        lupmn[i].resize(n + 1);
        lupm[i].resize(n + 1);
        if (i == 0) {
            for (int j = 0; j < n; j++) {
                wupm[i][j] = w[j];
                wup[i][j] = s[j];
                wupmx[i][j] = s[j];
                lupm[i][j] = l[j];
                lup[i][j] = p[j];
                lupmn[i][j] = s[j];
            }
            wupm[i][n] = n;
            wupmx[i][n] = 0;
            wup[i][n] = 0;
            lupm[i][n] = n;
            lupmn[i][n] = 0;
            lup[i][n] = 0;
        }
        else {
            for (int j = 0; j < n + 1; j++) {
                wupm[i][j] = wupm[i - 1][wupm[i - 1][j]];
                wup[i][j] = wup[i - 1][j] + wup[i - 1][wupm[i - 1][j]];
                wupmx[i][j] = max(wupmx[i - 1][j], wupmx[i - 1][wupm[i - 1][j]] - wup[i - 1][j]);
                lupm[i][j] = lupm[i - 1][lupm[i - 1][j]];
                lup[i][j] = lup[i - 1][j] + lup[i - 1][lupm[i - 1][j]];
                lupmn[i][j] = min(lupmn[i - 1][j], lupmn[i - 1][lupm[i - 1][j]] - lup[i - 1][j]);
            }
        }
    }
}

long long simulate2(int x, ll z);

long long simulate3(int x, ll z);

long long simulateult(int x, ll z);

long long simulate(int x, int z) {
    return simulateult(x, z);
}

long long simulateult(int x, ll z) {
    // cout << x << endl;
    while (x < n) {
        // cout << x << ' ' << z << '\n';
        if (z >= s[x]) {
            for (int i = 39; i >= 0; i--) {
                // cout << '\t' << i << ' ' << wupmx[i][x] << '\n';
                if (wupmx[i][x] <= z) {
                    z += wup[i][x];
                    x = wupm[i][x];
                }
            }
        }
        else {
            for (int i = 39; i >= 0; i--) {
                // cout << '\t' << i << ' ' << lup[i][x] << ' ' << lupmn[i][x] << '\n';
                if (lupmn[i][x] > z) {
                    z += lup[i][x];
                    x = lupm[i][x];
                }
            }
        }
        if (x < n) {
            if (z >= s[x]) {
                z += s[x];
                x = w[x];
            }
            else {
                z += p[x];
                x = l[x];
            }
            // cout << x << ' ' << z << '\n';
        }
    }
    return z;
}

• Subtask 1: 11 / 11
• Subtask 2: 26 / 26
• Subtask 3: 13 / 13
• Subtask 4: 0 / 12
• Subtask 5: 0 / 27
• Subtask 6: 0 / 11