oj.uz

Submission #468020

# Submission time Handle Problem Language Result Execution time Memory
468020 2021-08-25T21:49:48 Z UltraFalcon Fountain (eJOI20_fountain) C++17
100 / 100
 464 ms 44464 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 = 0;
            while (pow < log_n && vol_sum+par[lvl][pow].second < vi) {
                pow++;
            }
            vol_sum += par[lvl][pow-1].second;
            lvl = par[lvl][pow-1].first;
            //cerr << vol_sum+par[lvl][0].second << " -- dbg\n";
        }

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

        for (int pow=log_n-1; pow >= 0; pow--) {
            if (par[lvl][pow].first != -1 && vol_sum+par[lvl][pow].second < vi) {
                vol_sum += par[lvl][pow].second;
                lvl = par[lvl][pow].first;
            }
        }*/

        //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 313 ms 41960 KB Output is correct
2 Correct 340 ms 38740 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 313 ms 41960 KB Output is correct
9 Correct 340 ms 38740 KB Output is correct
10 Correct 2 ms 460 KB Output is correct
11 Correct 121 ms 21136 KB Output is correct
12 Correct 464 ms 44464 KB Output is correct
13 Correct 315 ms 39604 KB Output is correct
14 Correct 199 ms 38584 KB Output is correct
15 Correct 158 ms 37564 KB Output is correct