Submission #1023922

#	Time	Username	Problem	Language	Result	Execution time	Memory
1023922		Antonela	Fountain (eJOI20_fountain)	C++17	100 / 100	585 ms	36128 KiB

fountain

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n, q;
    cin>>n>>q;
    int L=log2(n)+1;
    int d[n+1], c[n+1];
    c[0]=d[0]=1e9+1;
    pair<int, long long>up[n+1][L+1];
    for(int i=1; i<=n; i++)
    {
        cin>>d[i]>>c[i];
    }
    stack<pair<long long, long long>>s;
    s.push({c[0], 0});
    for(int i=n; i; i--)
    {
        while(d[i]>=s.top().first)
        {
            s.pop();
        }
        up[i][0].first=s.top().second;
        up[i][0].second=c[s.top().second];
        for(int j=1; j<=L; j++)
        {
            up[i][j].first=up[up[i][j-1].first][j-1].first;
            up[i][j].second=up[i][j-1].second+up[up[i][j-1].first][j-1].second;
        }
        s.push({d[i], i});
    }
    while(q--)
    {
        int idx;
        long long val;
        cin>>idx>>val;
        val-=c[idx];
        if(val<=0)
        {
            cout<<idx<<"\n";
            continue;
        }
        for(int i=L; i>=0; i--)
        {
            if(up[idx][i].second<val)
            {
                val-=up[idx][i].second;
                idx=up[idx][i].first;
            }
        }
        cout<<up[idx][0].first<<"\n";
    }

    return 0;
}

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