Submission #1024820

#	Time	Username	Problem	Language	Result	Execution time	Memory
1024820		vjudge1	Fountain (eJOI20_fountain)	C++17	100 / 100	112 ms	37536 KiB

fountain

#include <bits/stdc++.h>

using namespace std;

vector<int> G[100005];
int n, q;
int dijametar[100005], kapacitet[100005];
int parent[100005][30], sobira[100005][30];

void dfs(int teme, int preth) {
    parent[teme][0]=preth;
    sobira[teme][0]=kapacitet[preth];
    for (auto next:G[teme]) {
        if (next!=preth)
            dfs(next, teme);
    }
}

void precomputeSparseMatrix() {
    for (int i=1;i<20;i++) {
        for (int teme=1;teme<=n+1;teme++) {
            if (parent[teme][i-1]!=-1) {
                parent[teme][i]=parent[parent[teme][i-1]][i-1];
                sobira[teme][i]=sobira[parent[teme][i-1]][i-1]+sobira[teme][i-1];
            }
        }
    }
}

int binary_lifting(int rezervoar, int voda) {
    voda-=kapacitet[rezervoar];
    for (int i=20;i>=0;i--) {
        if (parent[rezervoar][i]==-1) continue;
        //cout << "i=" << i << " parent=" << parent[rezervoar][i] << " " << sobira[rezervoar][i]+kapacitet[parent[rezervoar][i]] << endl;
        if (sobira[rezervoar][i]<voda) {
            voda-=sobira[rezervoar][i];
            rezervoar=parent[rezervoar][i];
        }
        //cout << "sega rezervoar=" << rezervoar << endl;
    }
    return parent[rezervoar][0];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> q;
    for (int i=1;i<=n;i++)
        cin >> dijametar[i] >> kapacitet[i];
    kapacitet[n+1]=2000000000;
    stack<pair<int,int> > s;
    s.push({INT_MAX, n+1});
    for (int i=n;i>=1;i--) {
        while (s.top().first<=dijametar[i])
            s.pop();
        G[i].push_back(s.top().second);
        G[s.top().second].push_back(i);
        //cout << "sleden na " << i << " e " << s.top().second << endl;
        s.push({dijametar[i], i});
    }
    memset(parent, -1, sizeof(parent));
    dfs(n+1, 0);
    precomputeSparseMatrix();
    while (q--) {
        int r, v;
        cin >> r >> v;
        if (kapacitet[r]>=v) cout << r << '\n';
        else {
            int rez=binary_lifting(r, v);
            if (rez==n+1) cout << 0 << '\n';
            else cout << rez << '\n';
        }
    }

    return 0;
}

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