Submission #827763

#	Time	Username	Problem	Language	Result	Execution time	Memory
827763		TahirAliyev	Fountain (eJOI20_fountain)	C++17	100 / 100	586 ms	38380 KiB

fountain

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pii pair<int, ll>

const int oo = 1e9 + 9;
const int MAX = 1e5 + 5, LOGMAX = 20;

int n, q;
int d[MAX], c[MAX];

pii par[LOGMAX][MAX];

int lift(int i, int l){
    int curl = l;
    int u = i;
    for (int j = LOGMAX - 1; j >= 0; j--)
    {
        if(curl - par[j][u].second > 0){
            curl -= par[j][u].second;
            u = par[j][u].first;
        }
    }
    return u;
}

int main(){
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
    {
        cin >> d[i] >> c[i];
    }
    stack<pii> s;
    for (int i = 1; i <= n; i++)
    {
        while(!s.empty() && s.top().first < d[i]){
            int a = s.top().second;
            s.pop();
            par[0][a] = {i, c[a]}; 
        }
        s.push({d[i], i});
    }
    while(!s.empty()){
        int a = s.top().second;
        s.pop();
        par[0][a] = {0, c[a]};
    }
    par[0][0] = {0, oo};

    for (int j = 1; j < LOGMAX; j++)
    {
        for (int i = 0; i <= n; i++)
        {
            int m = par[j - 1][i].first;
            par[j][i].first = par[j - 1][m].first;
            par[j][i].second = par[j - 1][i].second + par[j - 1][m].second ;
        }
    }

    while(q--){
        int r, v; cin >> r >> v;
        cout << lift(r, v) << '\n';
    }
}

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