oj.uz

Submission #894378

# Submission time Handle Problem Language Result Execution time Memory
894378 2023-12-28T07:45:42 Z viwlesxq Fountain (eJOI20_fountain) C++17
100 / 100
 1202 ms 38128 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin(), x.end()
#define size(x) (int)x.size()

template<class S, class T>
bool chmin(S &a, const T &b) {
    return a > b && (a = b) == b;
}
template<class S, class T>
bool chmax(S &a, const T &b) {
    return a < b && (a = b) == b;
}
const int inf = 1e9 + 7;
const int INF = 1e18 + 7;
const int mod = 1e9 + 7;

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, q;
    cin >> n >> q;
    int d[n + 1], c[n + 1];
    for (int i = 1; i <= n; ++i) {
        cin >> d[i] >> c[i];
    }
    vector<vector<int>> up(n + 1, vector<int> (17, 0));
    vector<vector<int>> sum(n + 1, vector<int> (17, 0));
    for (int i = 0; i < 17; ++i) {
        sum[0][i] = inf;
    }
    c[0] = d[0] = inf;
    stack<pair<int, int>> stk;
    stk.push({d[0], 0});
    for (int i = n; i >= 1; --i) {
        while (stk.top().first <= d[i]) {
            stk.pop();
        }
        up[i][0] = stk.top().second;
        sum[i][0] = c[stk.top().second];
        for (int j = 1; j < 17; ++j) {
            up[i][j] = up[up[i][j - 1]][j - 1];
            sum[i][j] = sum[up[i][j - 1]][j - 1] + sum[i][j - 1];
        }
        stk.push({d[i], i});
    }
    auto get = [&](int v, int d) {
        int res = c[v];
        for (int i = 16; i >= 0; --i) {
            if (d >> i & 1) {
                res += sum[v][i];
                v = up[v][i];
            }
        }
        return make_pair(res, v);
    };
    while (q--) {
        int r, v;
        cin >> r >> v;
        if (c[r] >= v) {
            cout << r << '\n';
            continue;
        }
        int lo = 0, hi = n;
        while (lo + 1 < hi) {
            int mid = (lo + hi) >> 1;
            if (get(r, mid).first >= v) {
                hi = mid;
            } else {
                lo = mid;
            }
        }
        cout << get(r, hi).second << '\n';
    }
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 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 604 KB Output is correct
6 Correct 2 ms 600 KB Output is correct
7 Correct 1 ms 604 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 843 ms 35724 KB Output is correct
2 Correct 811 ms 33284 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 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 604 KB Output is correct
6 Correct 2 ms 600 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 843 ms 35724 KB Output is correct
9 Correct 811 ms 33284 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 196 ms 20108 KB Output is correct
12 Correct 1202 ms 38128 KB Output is correct
13 Correct 461 ms 36180 KB Output is correct
14 Correct 243 ms 35836 KB Output is correct
15 Correct 125 ms 35924 KB Output is correct