Submission #589082

#	Time	Username	Problem	Language	Result	Execution time	Memory
589082		berr	Fountain (eJOI20_fountain)	C++17	30 / 100	523 ms	56848 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>>(31));

    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<31; 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--;
        int ans=0;

        int s=0;
        if(y<=a[x][1]) cout<<x+1<<"\n";
        else
        {
            y-=a[x][1];

            int tmpx=x;
            for(int l=30; l>=0; l--)
            {
                x=tmpx;
                ans=0;
                int tmp=s+(1<<l);
                if(tmp>n) continue;
                for(int i=30; i>=0&&ans<1e14; i--)
                {
                    if(tmp&(1<<i))
                    {
                        ans+=st[x][i][0];
                        x=st[x][i][1];
                    }
                }

                if(ans<y)
                {
                    s=tmp;
                }
            }
            ans=0;
            x=tmpx;
            s++;
            for(int i=30; i>=0; i--)
            {
                if(s&(1<<i))
                {
                    ans+=st[x][i][0];
                    x=st[x][i][1];
                }
            }
            if(ans>=1e9) cout<<0<<"\n";
            else cout<<x+1<<"\n";
            
        }
    }
}

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