Submission #967743

#	Time	Username	Problem	Language	Result	Execution time	Memory
967743		vjudge1	Fountain (eJOI20_fountain)	C++17	100 / 100	309 ms	46280 KiB

fountain

/**
 *　　　　　　  　　┏┓　　 　 ┏┓
 * 　　　　　  　　┏┛┗━━━━━━━┛┗━━━┓
 * 　　　　　  　　┃　　　　　　　 ┃ 　
 * 　　　　　  　　┃　　　━　　 　 ┃
 * 　　　　　  　　┃　＞　　　＜　 ┃
 * 　　　　　  　　┃　　　　　　　 ┃
 * 　　　　　  　　┃...　⌒　... 　┃
 * 　　　　　　  　┃              ┃
 * 　　　　　　  　┗━┓          ┏━┛
 * 　　　　　　　　　┃          ┃　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 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40