Submission #1133804

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133804		Paz15	Fountain (eJOI20_fountain)	C++20	100 / 100	120 ms	15812 KiB

fountain

//fast
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;

#define rep(n) for(int i = 0 ; i<n ; i++)
#define all(x) x.begin(),x.end()
#define pb push_back

const int base = 1e5+7;
int d[base];
int jump[base][17];
int ile[base][17];

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n,q;
    cin >> n >> q;
    rep(n) cin >> d[i] >> ile[i+1][0];
    vector<int> from;
    rep(n){
        while (from.size() && d[from.back()]<d[i]){
            jump[from.back()+1][0] = i+1;
            from.pop_back();
        }
        from.pb(i);
    }
    for (int i = 1 ; i<=16 ; i++){
        for (int j = 0 ; j<=n ; j++){
            jump[j][i] = jump[jump[j][i-1]][i-1];
            ile[j][i] = ile[j][i-1]+ile[jump[j][i-1]][i-1];
        }
    }
    while (q--){
        int r,v;
        cin >> r >> v;
        for (int i = 16 ; i>=0 ; i--){
            if (ile[r][i]<v){
                v-=ile[r][i];
                r = jump[r][i];
            }
        }
        cout << r << '\n';
    }
}

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