Submission #589125

#	Time	Username	Problem	Language	Result	Execution time	Memory
589125		berr	Fountain (eJOI20_fountain)	C++17	0 / 100	270 ms	54180 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
        {
            int ans=0;
            for(int i=30; i>=0; i--)
            {
                if(ans+st[x][i][0]<y)
                {
                    x=st[x][i][1];
                    ans+=st[x][i][0];
                }
            }

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

Compilation message (stderr)

fountain.cpp: In function 'int32_t main()':
fountain.cpp:67:13: warning: unused variable 'ans' [-Wunused-variable]
   67 |         int ans=0;
      |             ^~~
fountain.cpp:69:13: warning: unused variable 's' [-Wunused-variable]
   69 |         int s=0;
      |             ^

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