Submission #589146

#	Time	Username	Problem	Language	Result	Execution time	Memory
589146		berr	Fountain (eJOI20_fountain)	C++17	100 / 100	444 ms	40676 KiB

fountain

#include <bits/stdc++.h>
using namespace std;
#define int long long

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int n, q; cin>>n>>q;

    vector<array<int, 2>> a(n+1);


    for(int i=0; i<n; i++)
    {
        cin>>a[i][0]>>a[i][1];
    }

    stack<array<int, 2>> s;

    vector<vector<array<int, 2>>> st(n+1, vector<array<int, 2>>(20));

    s.push({(int)(1e13), n});

    int p=1e13;

        a[n]={p,p};
    s.push({a[n-1][0], n-1});


    st[n][0]={p, n};
    st[n-1][0]={p, n};
    for(int i=n-2; i>=0; i--)
    {

        while(a[i][0]>=s.top()[0])
        {
            s.pop();
        }

        if(s.size())
        {
            st[i][0]={a[s.top()[1]][1], s.top()[1]}; 
        }

        s.push({a[i][0], i});

    }


    for(int j=1; j<20; j++)
    {
        for(int i=0; i<=n; i++)
        {
            st[i][j]={st[i][j-1][0]+st[st[i][j-1][1]][j-1][0], st[st[i][j-1][1]][j-1][1]};
            st[i][j][0]=min((int)(1e15), st[i][j][0]);
        }
    }



    while(q--)
    {
        int x, y; cin>>x>>y;
        x--;
   
        if(y<=a[x][1]) cout<<x+1<<"\n";
        else
        {
            int ans=0;
            y-=a[x][1];
            for(int i=19; i>=0; i--)
            {
                if(ans+st[x][i][0]<y)
                {
                    ans+=st[x][i][0];
                    x=st[x][i][1];

                }
            }

            cout<<((st[x][0][1]==n)?0:st[x][0][1]+1)<<"\n";
        }
    }
}

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