oj.uz

Submission #967743

# Submission time Handle Problem Language Result Execution time Memory
967743 2024-04-22T18:10:29 Z vjudge1 Fountain (eJOI20_fountain) C++17
100 / 100
 309 ms 46280 KB 
/**
 *　　　　　　  　　┏┓　　 　 ┏┓
 * 　　　　　  　　┏┛┗━━━━━━━┛┗━━━┓
 * 　　　　　  　　┃　　　　　　　 ┃ 　
 * 　　　　　  　　┃　　　━　　 　 ┃
 * 　　　　　  　　┃　＞　　　＜　 ┃
 * 　　　　　  　　┃　　　　　　　 ┃
 * 　　　　　  　　┃...　⌒　... 　┃
 * 　　　　　　  　┃              ┃
 * 　　　　　　  　┗━┓          ┏━┛
 * 　　　　　　　　　┃          ┃　Code is far away from bug with the animal protecting　　　　　　　　　　
 * 　　　　　　　　　┃          ┃   神兽保佑,代码无bug
 * 　　　　　　　　　┃          ┃　　　　　　　　　　　
 * 　　　　　　　　　┃          ┃  　　　　　　
 * 　　　　　　　　　┃          ┃
 * 　　　　　　　　　┃          ┃　　　　　　　　　　　
 * 　　　　　　　　　┃          ┗━━━┓
 * 　　　　　　　　　┃              ┣┓
 * 　　　　　　　　　┃              ┏┛
 * 　　　　　　　　　┗┓┓┏━━━━━━━━┳┓┏┛
 * 　　　　　　　　　　┃┫┫       ┃┫┫
 * 　　　　　　　　　　┗┻┛       ┗┻┛
 */
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define FASTIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using PII = pair<int, int>;
#define F first
#define S second
#define pb push_back

const int MAXN = 1e5 + 5, LOGN = 25;
int n, q;
vector<int> length;
int nex[MAXN][LOGN];
int w[MAXN][LOGN];
void init() {
    for (int i = 1; i < LOGN; i++) {
        for (int cur = 1; cur <= n; cur++) {
            nex[cur][i] = nex[nex[cur][i - 1]][i - 1];
            w[cur][i] = w[cur][i - 1] + w[nex[cur][i - 1]][i - 1];
        }
    }
}
signed main() {
    FASTIO;
    cin >> n >> q;
    length.resize(n);
    for (int i = 0; i < n; i++) cin >> length[i] >> w[i + 1][0];

    stack<int> st;
    for (int i = n - 1; i >= 0; i--) {
        while (!st.empty() && length[st.top()] <= length[i]) st.pop();
        if (!st.empty()) nex[i + 1][0] = st.top() + 1;
        st.push(i);
    }

    init();

    // cout << w[1][1] << '\n';

    while (q--) {
        int start, water;
        cin >> start >> water;
        for (int i = LOGN - 1; i >= 0; i--) {
            // if (!nex[start][i]) continue;
            if (water > w[start][i]) {
                water -= w[start][i];
                start = nex[start][i];
                // cerr << "i : " << w[start][i] << '\n';
            }
        }

        cout << start << '\n';
        // cerr << water << '\n';
    }
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct
5 Correct 2 ms 4700 KB Output is correct
6 Correct 2 ms 4700 KB Output is correct
7 Correct 1 ms 4700 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 43800 KB Output is correct
2 Correct 201 ms 42836 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct
5 Correct 2 ms 4700 KB Output is correct
6 Correct 2 ms 4700 KB Output is correct
7 Correct 1 ms 4700 KB Output is correct
8 Correct 214 ms 43800 KB Output is correct
9 Correct 201 ms 42836 KB Output is correct
10 Correct 2 ms 4700 KB Output is correct
11 Correct 59 ms 27948 KB Output is correct
12 Correct 309 ms 46280 KB Output is correct
13 Correct 156 ms 45136 KB Output is correct
14 Correct 148 ms 44372 KB Output is correct
15 Correct 107 ms 44628 KB Output is correct