제출 #832363

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
832363		Pekiban	Fountain (eJOI20_fountain)	C++17	60 / 100	131 ms	31236 KiB

fountain

#include <bits/stdc++.h>

using namespace std;

const int mxN = 1e5+1, LOG = 20;
vector<int> adj[mxN];
pair<int, int> up[LOG][mxN];
int d[mxN], c[mxN];
void dfs(int s, int e) {
    for (auto u : adj[s]) {
        if (u == e) continue;
        up[0][u] = {s, c[s]};
        dfs(u, s);
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    d[0] = 1e9+1, c[0] = 1e9+1;
    for (int i = 0; i < LOG; ++i) {
        for (int j = 0; j < mxN; ++j) {
            up[i][j] = {-1, -1};
        }
    }
    up[0][0] = {-1, 0};
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; ++i) {
        cin >> d[i] >> c[i];
    }
    stack<pair<int, int>> s;    s.push({1e9+1, 0}); s.push({d[n], n}); adj[n].push_back(0); adj[0].push_back(n);
    int f[n+1]; f[n] = 0;
    for (int i = n-1; i >= 1; --i) {
        while (s.top().first <= d[i]) {
            s.pop();
        }
        f[i] = s.top().second;
        s.push({d[i], i});
        adj[i].push_back({f[i]}), adj[f[i]].push_back({i});
    }
    dfs(0, -1);
    for (int i = 1; i < LOG; ++i) {
        for (int j = 1; j <= n; ++j) {
            up[i][j] = {up[i-1][up[i-1][j].first].first, up[i-1][up[i-1][j].first].second + up[i-1][j].second};
        }
    }



    while (q--) {
        int r, v;
        cin >> r >> v;
        v -= c[r];
        for (int i = LOG-1; i >= 0; --i) {
            if (up[i][r].second <= v) {
                v -= up[i][r].second;
                r = up[i][r].first; 
            }
        }
        cout << (v > 0 ? up[0][r].first : r) << '\n';
    }
}

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