oj.uz

Submission #1019661

# Submission time Handle Problem Language Result Execution time Memory
1019661 2024-07-11T06:41:58 Z coolboy19521 Fountain (eJOI20_fountain) C++17
100 / 100
 204 ms 44676 KB 
#include "bits/stdc++.h"
#define int long long

using namespace std;

const int inf = 1e18 + 18;
const int sz = 1e5 + 5;
const int sm = 25;

vector<int> aj[sz];
int pf[sz], dm[sz];
int up[sm][sz];

void dfs(int v, int s = 0) {
    for (int i = 1; i < sm; i ++)
        up[i][v] = up[i-1][up[i-1][v]];

    pf[v] = s;

    for (int u : aj[v]) {
        up[0][u] = v;
        dfs(u, s + dm[u]);
    }
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int n, q;
    cin >> n >> q;

    vector<pair<int,int>> a;

    for (int i = 1; i <= n; i ++) {
        int d, c;
        cin >> d >> c;
        dm[i] = c;
        a.push_back(make_pair(d, i));
    }

    sort(begin(a),end(a),[](auto& l, auto& r){
        int dl = l.first;
        int dr = r.first;
        if (dl != dr)
            return dl < dr;
        int xl = l.second;
        int xr = r.second;
        return xl > xr;
    });

    set<int> rs = {n+1};

    for (auto it = rbegin(a); it != rend(a); it ++) {
        int v = it->second;
        int u = *rs.upper_bound(v);
        aj[u].push_back(v);
        rs.insert(v);
    }

    dfs(n+1);

    while (q --) {
        int r, v;
        cin >> r >> v;

        int s = pf[r];

        for (int i = sm-1; -1 < i; i --) {
            int p = up[i][r];
            if (s - pf[p] + dm[p] < v) {
                r = up[i][r];
            }
        }

        if (s - pf[r] + dm[r] < v)
            r = up[0][r];

        cout << r % (n+1) << '\n';
    }
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 23640 KB Output is correct
2 Correct 3 ms 23644 KB Output is correct
3 Correct 3 ms 23644 KB Output is correct
4 Correct 3 ms 23644 KB Output is correct
5 Correct 4 ms 23900 KB Output is correct
6 Correct 4 ms 23900 KB Output is correct
7 Correct 4 ms 23644 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 42172 KB Output is correct
2 Correct 153 ms 41272 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 23640 KB Output is correct
2 Correct 3 ms 23644 KB Output is correct
3 Correct 3 ms 23644 KB Output is correct
4 Correct 3 ms 23644 KB Output is correct
5 Correct 4 ms 23900 KB Output is correct
6 Correct 4 ms 23900 KB Output is correct
7 Correct 4 ms 23644 KB Output is correct
8 Correct 155 ms 42172 KB Output is correct
9 Correct 153 ms 41272 KB Output is correct
10 Correct 4 ms 23896 KB Output is correct
11 Correct 91 ms 30412 KB Output is correct
12 Correct 204 ms 44676 KB Output is correct
13 Correct 204 ms 38084 KB Output is correct
14 Correct 173 ms 36296 KB Output is correct
15 Correct 112 ms 35188 KB Output is correct