Submission #1005964

#	Time	Username	Problem	Language	Result	Execution time	Memory
1005964		overwatch9	Fountain (eJOI20_fountain)	C++17	100 / 100	826 ms	42360 KiB

fountain

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector <pair <int, int>> nums;
vector <vector <int>> nxt;
vector <vector <ll>> sum;
ll get_sum(int st, int len) {
    if (len == 0)
        return nums[st].second;
    ll ans = 0;
    for (int i = 0; i < 20; i++) {
        if ((1 << i) & len) {
            ans += sum[st][i];
            st = nxt[st][i];
        }
    }
    return ans;
}
int get_node(int st, int len) {
    int ans = st;
    for (int i = 19; i >= 0; i--) {
        if ((1 << i) & len)
            ans = nxt[ans][i];
    }
    return ans;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, q;
    cin >> n >> q;
    nums.resize(n+1);
    nxt = vector <vector <int>> (n+1, vector <int> (20));
    sum = vector <vector <ll>> (n+1, vector <ll> (20));
    for (int i = 1; i <= n; i++) {
        cin >> nums[i].first >> nums[i].second;
    }
    multiset <pair <int, int>> s;
    for (int i = n; i > 0; i--) {
        pair <int, int> tp = {nums[i].first+1, 0};
        auto it = s.lower_bound(tp);
        if (it == s.end()) {
            nxt[i][0] = 0;
        } else {
            nxt[i][0] = it->second;
        }
        while (!s.empty() && s.begin()->first <= nums[i].first)
            s.erase(s.begin());
        s.insert({nums[i].first, i});
    }
    for (int i = n; i >= 1; i--) {
        for (int j = 1; j < 20; j++)
            nxt[i][j] = nxt[nxt[i][j-1]][j-1];
        continue;
    }
    for (int i = n; i >= 1; i--) {
        sum[i][0] = nums[i].second;
        for (int j = 1; j < 20; j++) {
            sum[i][j] = sum[i][j-1] + sum[nxt[i][j-1]][j-1];
        }
        continue;
    }
    while (q--) {
        int r;
        ll v;
        cin >> r >> v;
        int lo = 1, hi = n - r + 2;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            ll s = get_sum(r, mid);
            if (s < v)
                lo = mid + 1;
            else
                hi = mid;
        }
        int ans = get_node(r, lo-1);
        cout << ans << '\n';
    }
}

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