Submission #736143

#	Time	Username	Problem	Language	Result	Execution time	Memory
736143		Toxtaq	Fountain (eJOI20_fountain)	C++17	100 / 100	696 ms	34352 KiB

fountain

#include<bits/stdc++.h>
using namespace std;
vector<int>d, c; /// diameter and capacity
vector<vector<long long>>table, calc;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    d.resize(n + 1);
    c.resize(n + 1);
    vector<int>next(n + 1), LOG(n + 1);
    LOG[1] = 0;
    for(int i = 2;i <= n;++i)LOG[i] = LOG[i / 2] + 1;
    table.resize(LOG[n] + 1);
    calc.resize(LOG[n] + 1);
    for(int i = 0;i <= LOG[n];++i){
        table[i].resize(n + 1);
        calc[i].resize(n + 1);
    }
    d[0] = 2e9;
    c[0] = 2e9;
    for(int i = 1;i <= n;++i){
        cin >> d[i] >> c[i];
    }
    stack<int>st;
    st.push(0);
    for(int i = n;i >= 1;--i){
        while(d[st.top()] <= d[i]){
            st.pop();
        }
        next[i] = st.top();
        st.push(i);
    }
    table[0][0] = 0;
    for(int i = 0;i <= n;++i){
        table[0][i] = next[i];
        calc[0][i] = c[next[i]];
    }
    for(int i = 1;i <= LOG[n];++i){
        for(int j = 0;j <= n;++j){
            table[i][j] = table[i - 1][table[i - 1][j]];
            calc[i][j] = calc[i - 1][j] + calc[i - 1][table[i - 1][j]];
        }
    }
    while(q--){
        int node, v;
        cin >> node >> v;
        int l = 0, r = n + 1, ans = 0;
        while(r >= l){
            int mid = (l + r) >> 1;
            int cpy = mid, cpyn = node;
            long long C = c[node];
//            cout << "MID: " << mid << ": \n";
            for(int i = LOG[n];i >= 0;--i){
                if(cpy >= (1 << i)){
                    cpy -= (1 << i);
                    C += calc[i][cpyn];
                    cpyn = table[i][cpyn];
                    if(C >= v){
                        break;
                    }
//                    cout << "NODE: " << cpyn << "\n";
                }
            }
//            cout << C << "\n\n";
            if(C >= v){
                ans = cpyn;
                r = mid - 1;
            }
            else{
                l = mid + 1;
            }
        }
        cout << ans << '\n';
    }
}

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40