oj.uz

Submission #964950

# Submission time Handle Problem Language Result Execution time Memory
964950 2024-04-17T18:35:19 Z zxcigan Fountain (eJOI20_fountain) C++17
100 / 100
 255 ms 93360 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;

const int N = 1e6 + 1;
const int mod = 1e9 + 7;

template <typename T>
bool umx(T& a, T b) {
    return (a < b ? a = b, 1 : 0);
}
template <typename T>
bool umn(T& a, T b) {
    return (a > b ? a = b, 1 : 0);
}
int to[20][N];
ll s[20][N];
void solve () {
    int n, q;
    cin >> n >> q;
    vector<int> d (n + 1), c (n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> d[i] >> c[i];
    }
    vector<int> bigr(n + 1);
    vector<int> ve;
    vector<ll> pref (n + 1);
    for (int i = 1; i <= n; ++i) {
        while ((int)ve.size() && d[ve.back()] < d[i]) {
            bigr[ve.back()] = i;
            ve.pop_back();
        }
        ve.push_back(i);
    }
    for (int i = n; i >= 1; --i) {
        to[0][i] = bigr[i];
        s[0][i] = c[bigr[i]];
        for (int l = 1; l < 20; ++l) {
            to[l][i] = to[l - 1][to[l - 1][i]];
            s[l][i] = s[l - 1][i] + s[l - 1][to[l - 1][i]];
        }
    }
    while (q--) {
        int r, v;
        cin >> r >> v;
        if (v <= c[r]) {
            cout << r << "\n";
            continue;
        }
        v -= c[r];
        for (int l = 19; l >= 0; --l) {
            if (s[l][r] < v) {
                v -= s[l][r];
                r = to[l][r];
            }
        }

        cout << to[0][r] << "\n";
    }
}

signed main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
    //    freopen ("input.txt", "r", stdin);
//    freopen ("output.txt", "w", stdout);
#endif

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    while (T--) solve();
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 80468 KB Output is correct
2 Correct 9 ms 80476 KB Output is correct
3 Correct 10 ms 80476 KB Output is correct
4 Correct 10 ms 80396 KB Output is correct
5 Correct 11 ms 80476 KB Output is correct
6 Correct 9 ms 80456 KB Output is correct
7 Correct 9 ms 80476 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 90128 KB Output is correct
2 Correct 159 ms 91416 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 80468 KB Output is correct
2 Correct 9 ms 80476 KB Output is correct
3 Correct 10 ms 80476 KB Output is correct
4 Correct 10 ms 80396 KB Output is correct
5 Correct 11 ms 80476 KB Output is correct
6 Correct 9 ms 80456 KB Output is correct
7 Correct 9 ms 80476 KB Output is correct
8 Correct 161 ms 90128 KB Output is correct
9 Correct 159 ms 91416 KB Output is correct
10 Correct 10 ms 80448 KB Output is correct
11 Correct 65 ms 87196 KB Output is correct
12 Correct 255 ms 93360 KB Output is correct
13 Correct 151 ms 93104 KB Output is correct
14 Correct 112 ms 92240 KB Output is correct
15 Correct 87 ms 93008 KB Output is correct