oj.uz

Submission #468018

# Submission time Handle Problem Language Result Execution time Memory
468018 2021-08-25T21:40:52 Z UltraFalcon Fountain (eJOI20_fountain) C++17
100 / 100
 474 ms 44652 KB 
#include <bits/stdc++.h>
#define int long long

using namespace std;

const int INF = 1e18;

vector<vector<pair<int, int>>> adj;
vector<vector<pair<int, int>>> par;

void dfs(int v) {
    //cerr << v << " -- v start\n";
    for (auto [u, ci] : adj[v]) {
        par[u][0] = {v, ci};
        dfs(u);
    }
    //cerr << v << " -- v end\n"; 
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

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

    int log_n = __lg(n-1) + 1;

    //cerr << log_n;

    vector<pair<int, int>> resv; // di, ci
    for (int i=0; i<n; i++) {
        int di, ci;
        cin >> di >> ci;
        resv.push_back({di, ci});
    }
    resv.push_back({INF, INF}); // Add the waterway
    reverse(resv.begin(), resv.end());

    adj.assign(n+1, {});

    vector<int> st; 
    st.push_back(0);
    for (int i=1; i<=n; i++) {
        while (resv[st.back()].first <= resv[i].first) {
            //cerr << st.back() << "\n";
            st.pop_back();
        }
        adj[st.back()].push_back({i, resv[i].second});
        //adj[i].push_back({st.back(), resv[i].second});
        st.push_back(i);
    }

    //cerr << "run1\n";

    // Compute binary lift
    par.assign(n+1, vector<pair<int, int>>(log_n, {-1, INF}));
    dfs(0);

    //cerr << "run2\n";

    for (int k=1; k<log_n; k++) {
        for (int i=1; i<=n; i++) {
            if (par[i][k-1].first < 0) { continue; }
            par[i][k] = {par[par[i][k-1].first][k-1].first, par[i][k-1].second + par[par[i][k-1].first][k-1].second};
            //cerr << par[i][k].first << " ";
        }
        //cerr << "\n";
    }
    
    //cerr << "run3\n";

    //return 0;

    for (int i=0; i<q; i++) {
        int ri, vi;
        cin >> ri >> vi;

        //cerr << "run0" << "\n";
        

        int lvl = n - ri + 1;
        int vol_sum = 0;
        while (vol_sum+par[lvl][0].second < vi) {
            //cerr << vol_sum+par[lvl][0].second << " -- dbg2\n";
            int pow = 1;
            while (pow-1 < log_n && vol_sum+par[lvl][pow-1].second < vi) {
                pow++;
            }
            vol_sum += par[lvl][pow-2].second;
            lvl = par[lvl][pow-2].first;
            //cerr << vol_sum+par[lvl][0].second << " -- dbg\n";
        }

        /*
        int lvl = n - ri + 1;
        int vol_sum = 0;
        int pow = log_n;

        while (pow > 1) {
            pow--;
            if (vol_sum+par[lvl][pow-1].second > vi) {
                vol_sum += par[lvl][pow-1].second;
                lvl = par[lvl][pow-1];
            }
        }*/

        //cerr << vol_sum << "\n";
        //cerr << "calc end\n";

        if (lvl == 0) {
            cout << 0 << "\n";
        } else {
            cout << n - lvl + 1 << "\n";
        }
    }

}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 2 ms 588 KB Output is correct
6 Correct 2 ms 588 KB Output is correct
7 Correct 1 ms 460 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 302 ms 42012 KB Output is correct
2 Correct 339 ms 38720 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 2 ms 588 KB Output is correct
6 Correct 2 ms 588 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 302 ms 42012 KB Output is correct
9 Correct 339 ms 38720 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 114 ms 21152 KB Output is correct
12 Correct 474 ms 44652 KB Output is correct
13 Correct 296 ms 39608 KB Output is correct
14 Correct 199 ms 38612 KB Output is correct
15 Correct 155 ms 37692 KB Output is correct