제출 #1286197

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1286197		okahak71	Fountain (eJOI20_fountain)	C++20	30 / 100	751 ms	79632 KiB

fountain

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int LG = 41; // enough for n up to ~1e12 (overkill for usual constraints)

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    if (!(cin >> n >> q)) return 0;
    vector<pair<ll,ll>> a(n+1);
    for(int i=1;i<=n;i++) cin >> a[i].first >> a[i].second;

    vector<vector<int>> up(LG, vector<int>(n+1, 0));
    // sm as __int128 to avoid overflow
    vector<vector<__int128>> sm(LG, vector<__int128>(n+1, 0));

    deque<pair<ll,int>> st;
    for(int i=1;i<=n;i++){
        ll d = a[i].first;
        while(!st.empty() && st.front().first < d){
            int id = st.front().second; st.pop_front();
            up[0][id] = i;
            sm[0][id] = (__int128)a[id].second;
        }
        st.push_front({d, i});
    }
    while(!st.empty()){
        int id = st.front().second; st.pop_front();
        up[0][id] = 0;
        sm[0][id] = (__int128)a[id].second;
    }

    // build binary lifting tables, clamp sums to a very large sentinel to avoid wrap
    const __int128 INF = (__int128)9e18; // big enough sentinel
    for(int k=1;k<LG;k++){
        for(int v=1; v<=n; v++){
            int mid = up[k-1][v];
            up[k][v] = (mid ? up[k-1][mid] : 0);
            __int128 s = sm[k-1][v];
            if(mid) s += sm[k-1][mid];
            if(s > INF) s = INF;
            sm[k][v] = s;
        }
    }

    auto jump_k = [&](int x, long long k){
        // jump k single-step moves via up[0] powers
        for(int b=0; b<LG && x; ++b){
            if(k & (1LL<<b)) x = up[b][x];
        }
        return x;
    };

    while(q--){
        int cur; ll v_ll; cin >> cur >> v_ll;
        __int128 v = (__int128)v_ll;
        bool finished = false;

        while(cur && !finished){
            bool moved = false;
            for(int k = LG-1; k >= 0; --k){
                if(sm[k][cur] <= v){
                    if(sm[k][cur] == v){
                        // exactly fills block of size 2^k starting at cur
                        if(k == 0){
                            // last filled is cur itself
                            // cur remains cur
                        } else {
                            cur = jump_k(cur, (1LL<<k) - 1);
                        }
                        finished = true;
                    } else {
                        v -= sm[k][cur];
                        cur = up[k][cur];
                    }
                    moved = true;
                    break;
                }
            }
            if(!moved) break;
        }
        cout << cur << '\n';
    }
    return 0;
}

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