제출 #894378

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
894378		viwlesxq	Fountain (eJOI20_fountain)	C++17	100 / 100	1202 ms	38128 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});
    }
    auto get = [&](int v, int d) {
        int res = c[v];
        for (int i = 16; i >= 0; --i) {
            if (d >> i & 1) {
                res += sum[v][i];
                v = up[v][i];
            }
        }
        return make_pair(res, v);
    };
    while (q--) {
        int r, v;
        cin >> r >> v;
        if (c[r] >= v) {
            cout << r << '\n';
            continue;
        }
        int lo = 0, hi = n;
        while (lo + 1 < hi) {
            int mid = (lo + hi) >> 1;
            if (get(r, mid).first >= v) {
                hi = mid;
            } else {
                lo = mid;
            }
        }
        cout << get(r, hi).second << '\n';
    }
}

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