oj.uz

Submission #839703

# Submission time Handle Problem Language Result Execution time Memory
839703 2023-08-30T15:30:45 Z tshabanov7 Fountain (eJOI20_fountain) C++17
30 / 100
 111 ms 28000 KB 
#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);
        }
    };

    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
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 28000 KB Output is correct
2 Correct 111 ms 27000 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -