제출 #1286200

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1286200		okahak71	Fountain (eJOI20_fountain)	C++20	0 / 100	310 ms	64568 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;

const ll inf = LLONG_MAX;

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++){
            if (!up[i - 1][j]) sm[i][j] = inf;
			else {
				if (!up[i - 1][up[i - 1][j]]) sm[i][j] = inf;
				else {
					up[i][j] = up[i - 1][up[i - 1][j]];
					sm[i][j] = sm[i - 1][j] + sm[i - 1][up[i - 1][j]];
				}
			}
        }
    }
    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];
                        cout << cur << ' ' << j << ' ' << i << endl;}
                    }
                    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: 0 / 30
• Subtask 3: 0 / 40