Submission #1284002

#	Time	Username	Problem	Language	Result	Execution time	Memory
1284002		canhnam357	Fountain (eJOI20_fountain)	C++20	30 / 100	144 ms	32160 KiB

fountain

#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define N 100000
#define LG 17
pair<long long, int> st[N][LG];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    vector<tuple<int, int, int>> a;
    for (int i = 0; i < n; i++) {
        int d, c;
        cin >> d >> c;
        a.emplace_back(d, c, i);
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < LG; j++) {
            st[i][j] = {-1, -1};
        }
    }
    sort(a.rbegin(), a.rend());
    set<int> s;
    for (int l = 0, r = 0; r < n; r++) {
        while (get<0>(a[r]) != get<0>(a[l])) {
            s.insert(get<2>(a[l++]));
        }
        auto it = s.lower_bound(get<2>(a[r]));
        if (s.empty() || it == s.end()) {
            st[get<2>(a[r])][0] = {get<1>(a[r]), n};
        }
        else {
            st[get<2>(a[r])][0] = {get<1>(a[r]), *it};
        }
    }
    for (int j = 1; j < LG; j++) {
        for (int i = 0; i + (1 << j) <= n; i++) {
            if (st[i][j - 1].second == n || st[st[i][j - 1].second][j - 1].second == -1) continue;
            st[i][j] = {st[i][j - 1].first + st[st[i][j - 1].second][j - 1].first, 
                        st[st[i][j - 1].second][j - 1].second};
        }
    }
    while (q--) {
        int r, v;
        cin >> r >> v;
        r--;
        for (int i = LG - 1; i >= 0 && r < n; i--) {
            if (st[r][i].first == -1) continue;
            if (v > st[r][i].first) {
                v -= st[r][i].first;
                r = st[r][i].second;
            }
        }
        if (r == n) r = -1;
        cout << r + 1 << '\n';
    }
    return 0;
}

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