Submission #1163252

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163252		SzymonKrzywda	Fountain (eJOI20_fountain)	C++20	100 / 100	344 ms	16408 KiB

fountain

#include <iostream>
#include <vector>

using ll = long long;
using namespace std;

const int LOGK = 17, MAXN = 1e5 + 7;

int jump[MAXN][LOGK];
int suma[MAXN][LOGK];


int main(){
    int n, q;
    
    cin >> n >> q;

    int a, b;

    vector<pair<int, int>> tab;

    for (int i = 0; i < n; i++){
        cin >> a >> b;
        tab.push_back({a, b});
    }
    tab.push_back({2e9, 2e9});

    vector<int> stos;
    stos.push_back(n);

    for (int i = n - 1; i >= 0; i--){
        while (tab[stos.back()].first <= tab[i].first) stos.pop_back();
        jump[i][0] = stos.back();
        suma[i][0] = tab[stos.back()].second;
        stos.push_back(i);
    }

    jump[n][0] = n;

    for (int k = 1; k < LOGK; k++){
        for (int v = 0; v <= n; v++){
            jump[v][k] = jump[jump[v][k - 1]][k - 1];
            if (jump[v][k] == n) suma[v][k] = 2e9;
            else suma[v][k] = suma[v][k - 1] + suma[jump[v][k - 1]][k - 1];
        }
    }


    while (q--){
        cin >> a >> b;
        a--;

        int aktsuma = tab[a].second;

        for (int k = LOGK - 1; k >= 0; k--){
            if (jump[a][k] == n) continue;
            //cout << k << ' ' << a << ' ' << jump[a][k] << ' ' << aktsuma << ' ' << suma[a][k] << '\n';
            if (aktsuma + suma[a][k] < b){
                aktsuma += suma[a][k];
                a = jump[a][k];
            }
        }
        //cout << a << '\n';

        if (aktsuma < b) a = jump[a][0];
        if (a == n) a = -1;

        cout << a + 1 << '\n';
    }


    return 0;
}

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