제출 #894379

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
894379		viwlesxq	Fountain (eJOI20_fountain)	C++17	100 / 100	345 ms	37480 KiB

fountain

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin(), x.end()
#define size(x) (int)x.size()

template<class S, class T>
bool chmin(S &a, const T &b) {
    return a > b && (a = b) == b;
}
template<class S, class T>
bool chmax(S &a, const T &b) {
    return a < b && (a = b) == b;
}
const int inf = 1e9 + 7;
const int INF = 1e18 + 7;
const int mod = 1e9 + 7;

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, q;
    cin >> n >> q;
    int d[n + 1], c[n + 1];
    for (int i = 1; i <= n; ++i) {
        cin >> d[i] >> c[i];
    }
    vector<vector<int>> up(n + 1, vector<int> (17, 0));
    vector<vector<int>> sum(n + 1, vector<int> (17, 0));
    for (int i = 0; i < 17; ++i) {
        sum[0][i] = inf;
    }
    c[0] = d[0] = inf;
    stack<pair<int, int>> stk;
    stk.push({d[0], 0});
    for (int i = n; i >= 1; --i) {
        while (stk.top().first <= d[i]) {
            stk.pop();
        }
        up[i][0] = stk.top().second;
        sum[i][0] = c[stk.top().second];
        for (int j = 1; j < 17; ++j) {
            up[i][j] = up[up[i][j - 1]][j - 1];
            sum[i][j] = sum[up[i][j - 1]][j - 1] + sum[i][j - 1];
        }
        stk.push({d[i], i});
    }
    while (q--) {
        int r, v;
        cin >> r >> v;
        if (c[r] >= v) {
            cout << r << '\n';
            continue;
        }
        v -= c[r];
        for (int i = 16; i >= 0; --i) {
            if (sum[r][i] < v) {
                v -= sum[r][i];
                r = up[r][i];
            }
        }
        cout << up[r][0] << '\n';
    }
}

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40