제출 #1286194

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

fountain

#include <bits/stdc++.h>
#define ll long long
#define vec vector
#define ss second
#define ff first
#define endl '\n'
#define all(X) X.begin(), X.end()
using namespace std;

void _(){
    ll n, q; cin >> n >> q; vec<pair<ll , ll>>a(n + 1);
    deque<pair<ll, ll>>dq; const ll lg = 41;
    vec<vec<ll>>up(lg, vec<ll>(n + 1, 0)), sm(lg, vec<ll>(n + 1, 0));
    for(ll i = 1; i <= n; i++){
        cin >> a[i].ff >> a[i].ss;
        ll d = a[i].ff;
        if(i){
            while(!dq.empty() and dq.front().ff < d){
                auto [dm, id] = dq.front();
                dq.pop_front();
                up[0][id] = i, sm[0][id] = a[id].ss;
            }
        }
        dq.push_front({d, i});
    }
    while(!dq.empty()){
        auto [dm , id] = dq.front();
        dq.pop_front(); sm[0][id] = a[id].ss;
    }
    for(ll i = 1; i < lg; i++){
        for(ll j = 1; j <= n; j++){
            up[i][j] = up[i - 1][up[i - 1][j]];
            sm[i][j] = sm[i - 1][j] + ( up[i - 1][j] ? sm[i - 1][up[i - 1][j]] : 0);
        }
    }
    while(q--){
        ll cur, v; cin >> cur >> v;
        bool ok = 1;
        while(cur and v > 0){
            ok = 0;
            for(ll i = lg - 1 ; i >= 0; i--){
                if(sm[i][cur] <= v){
                    v -= sm[i][cur];
                    if(!v){
                        for(ll j = 0; j < i and cur; j++) cur = up[j][cur];
                    }
                    else cur = up[i][cur]; ok = 1; break;
                }
            }
            if(!ok) break;
        }
        cout << cur << endl;
    }
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); _();
}

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