제출 #465486

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
465486		dfistric	Fountain (eJOI20_fountain)	C++14	100 / 100	784 ms	22976 KiB

fountain

#include <bits/stdc++.h>

#define f first
#define s second

using namespace std;

typedef pair <int, int> pii;

const int MAXN = 1e5 + 5;

int n, q;
pii info[MAXN], child_pow2[MAXN][20];

vector <pii> available;

int main()
{
    cin >> n >> q;
    for(int i = 1; i <= n; i++) cin >> info[i].f >> info[i].s;

    for(int i = n; i >= 1; i--){
        while(!available.empty() && available.back().f <= info[i].f) available.pop_back();

        if(available.empty()) child_pow2[i][0] = {0, info[i].s};
        else child_pow2[i][0] = {available.back().s, info[i].s};

        available.push_back({info[i].f, i});
    }

    for(int j = 1; j < 20; j++){
        for(int i = 1; i <= n; i++){
            pii child = child_pow2[child_pow2[i][j - 1].f][j - 1];
            child_pow2[i][j] = {child.f, child_pow2[i][j - 1].s + child.s};
        }
    }

    while(q--){
        int ind, amount;
        cin >> ind >> amount;

        for(int i = 19; i >= 0; i--){
            if(amount > child_pow2[ind][i].s){
                amount -= child_pow2[ind][i].s;
                ind = child_pow2[ind][i].f;
            }
        }

        cout << ind << '\n';
    }

return 0;
}

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