oj.uz

답안 #468019

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
468019 2021-08-25T21:48:43 Z UltraFalcon Fountain (eJOI20_fountain) C++17
100 / 100
 447 ms 44480 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Correct 316 ms 42076 KB Output is correct
2 Correct 325 ms 38732 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 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 316 ms 42076 KB Output is correct
9 Correct 325 ms 38732 KB Output is correct
10 Correct 2 ms 460 KB Output is correct
11 Correct 126 ms 21148 KB Output is correct
12 Correct 447 ms 44480 KB Output is correct
13 Correct 321 ms 39592 KB Output is correct
14 Correct 208 ms 38540 KB Output is correct
15 Correct 176 ms 37640 KB Output is correct