Submission #839704

#	Time	Username	Problem	Language	Result	Execution time	Memory
839704		tshabanov7	Fountain (eJOI20_fountain)	C++17	100 / 100	159 ms	35132 KiB

fountain

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;

    vector<int> d(n), c(n);
    for (int i = 0; i < n; i++) {
        cin >> d[i] >> c[i];
    }

    vector<int> gR(n, n), stk;
    for (int i = 0; i < n; i++) {
        while (!stk.empty() && d[stk.back()] < d[i]) {
            gR[stk.back()] = i;
            stk.pop_back();
        }
        stk.push_back(i);
    }

    vector<vector<pair<int, int>>> qry(n);
    for (int i = 0; i < q; i++) {
        int r, v;
        cin >> r >> v;
        r--;
        qry[r].emplace_back(v, i);
    }

    vector<vector<int>> adj(n + 1);
    for (int i = 0; i < n; i++) {
        adj[gR[i]].push_back(i);
    }

    ll t;
    set<pair<ll, int>> S;
    vector<int> ans(q);

    function<void(int)> dfs = [&](int v) {
        S.insert({0 - t, v});
        t += c[v];

        for (auto [w, id] : qry[v]) {
            auto it = S.lower_bound({w - t, -1});
            if (it == S.end()) {
                ans[id] = 0;
            } else {
                ans[id] = it->second + 1;
            }
        }

        for (auto to : adj[v]) {
            dfs(to);
        }

        t -= c[v];
        S.erase({0 - t, v});
    };

    for (auto to : adj[n]) {
        S.clear();
        t = 0;
        dfs(to);
    }

    for (int i = 0; i < q; i++) {
        cout << ans[i] << '\n';
    }

    return 0;
}

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