제출 #1286195

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

fountain

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

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

    vector<vector<ll>> up(LG, vector<ll>(n+1, 0));
    vector<vector<ll>> sm(LG, vector<ll>(n+1, 0));
    deque<pair<ll,ll>> dq;

    // build up[0] and sm[0]
    for(int i=1;i<=n;i++){
        ll d = a[i].first;
        while(!dq.empty() && dq.front().first < d){
            auto [dm,id] = dq.front(); dq.pop_front();
            up[0][id] = i;
            sm[0][id] = a[id].second;
        }
        dq.push_front({d,i});
    }
    while(!dq.empty()){
        auto [dm,id] = dq.front(); dq.pop_front();
        up[0][id] = 0;
        sm[0][id] = a[id].second;
    }

    // build binary lifting tables
    for(int k=1;k<LG;k++){
        for(int v=1; v<=n; v++){
            ll mid = up[k-1][v];
            up[k][v] = (mid ? up[k-1][mid] : 0);
            sm[k][v] = sm[k-1][v] + (mid ? sm[k-1][mid] : 0);
            // be careful with overflow if capacities are huge; use 128-bit if needed
        }
    }

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

    while(q--){
        ll cur, v; cin >> cur >> v;
        // simulate
        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 2^k reservoirs starting at cur
                        // last filled is (2^k - 1) single-step moves from cur
                        if(k == 0){
                            // if k==0 and sm[0][cur]==v, last filled is cur itself
                            // cur remains cur and we're finished
                        } 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; // can't move further
        }
        cout << cur << '\n';
    }
    return 0;
}

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