oj.uz

Submission #1005964

# Submission time Handle Problem Language Result Execution time Memory
1005964 2024-06-23T09:31:08 Z overwatch9 Fountain (eJOI20_fountain) C++17
100 / 100
 826 ms 42360 KB 
#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 396 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 2 ms 860 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 2 ms 604 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 458 ms 38936 KB Output is correct
2 Correct 536 ms 36440 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 396 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 2 ms 860 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 2 ms 604 KB Output is correct
8 Correct 458 ms 38936 KB Output is correct
9 Correct 536 ms 36440 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 211 ms 20820 KB Output is correct
12 Correct 826 ms 42360 KB Output is correct
13 Correct 605 ms 38060 KB Output is correct
14 Correct 279 ms 36436 KB Output is correct
15 Correct 202 ms 36948 KB Output is correct