Submission #1129236

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129236		jakubmz2	Fountain (eJOI20_fountain)	C++20	100 / 100	231 ms	31300 KiB

fountain

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

const ll MAXN = 1e5 + 5;
const ll MAXK = 17;

pair<ll,ll> font[MAXN];
pair<ll,ll> jmp[MAXN][MAXK];

vector<pair<ll,ll>> nast;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll n, q;
    cin >> n >> q;
    ll a, b;
    for(int i = 0; i < n; ++i){
        cin >> a >> b;
        font[i] = {a,b};
    }
    for(int i = n - 1; i >= 0; --i){
        //cout << "\n";
        //cout << i << " i\n";
        //cout << font[i].first << " " << font[i].second << " font\n";
        while(nast.size() > 0 and nast.back().first <= font[i].first){
            nast.pop_back();
        }
        nast.push_back({font[i].first, i});
        for(auto u : nast){
            //cout << u.first << " " << u.second << " nast\n";
        }
        if(nast.size() == 1){
            //cout << "#\n";
            jmp[i][0] = {n, font[i].second};
        }
        else{
            //cout << "$\n";
            int p = 0;
            int k = nast.size() - 1;
            while(p != k){
                int sr = (p + k + 1) / 2;
                if(nast[sr].first <= font[i].first){
                    k = sr - 1;
                }
                else{
                    p = sr;
                }
            }
            jmp[i][0].first = nast[p].second;
            jmp[i][0].second = font[i].second;
            int j = 0;
            while(jmp[i][j].first != n and j < MAXK and jmp[i][j].first != 0){
                auto nxt = jmp[i][j];
                if(jmp[nxt.first][j].first == 0) break;
                jmp[i][j + 1].first = jmp[nxt.first][j].first;
                jmp[i][j + 1].second = jmp[i][j].second + jmp[nxt.first][j].second;
                j++;
            }
        }
        // for(int j = 0; j < 8; ++j){
        //     cout << jmp[i][j].first << " " << jmp[i][j].second << " " << j << " jmp2\n";
        // }
    }

    // for(int i = 0; i < n; ++i){
    //     cout << "i: " << i << "\n";
    //     for(int j = 0; j < 8; ++j){
    //         cout << jmp[i][j].first << " " << jmp[i][j].second << " " << j << " jmp\n";
    //     }
    // }


    for(int i = 0; i < q; ++i){
        cin >> a >> b;
        a--;
        for(int j = MAXK - 1; j >= 0; --j){
            if(jmp[a][j].second < b and jmp[a][j].first != 0){
                b -= jmp[a][j].second;
                a = jmp[a][j].first;
            }
        }
        cout << (a == n ? 0 : a + 1) << "\n";
    }
    return 0;
}

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