oj.uz

Submission #589132

# Submission time Handle Problem Language Result Execution time Memory
589132 2022-07-04T09:37:33 Z berr Fountain (eJOI20_fountain) C++17
100 / 100
 481 ms 57476 KB 
#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--;
   
        if(y<=a[x][1]) cout<<x+1<<"\n";
        else
        {
            int ans=0;
            y-=a[x][1];
            for(int i=30; 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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 1 ms 852 KB Output is correct
5 Correct 2 ms 880 KB Output is correct
6 Correct 2 ms 852 KB Output is correct
7 Correct 2 ms 844 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 317 ms 53912 KB Output is correct
2 Correct 343 ms 50080 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 1 ms 852 KB Output is correct
5 Correct 2 ms 880 KB Output is correct
6 Correct 2 ms 852 KB Output is correct
7 Correct 2 ms 844 KB Output is correct
8 Correct 317 ms 53912 KB Output is correct
9 Correct 343 ms 50080 KB Output is correct
10 Correct 3 ms 888 KB Output is correct
11 Correct 150 ms 31280 KB Output is correct
12 Correct 481 ms 57476 KB Output is correct
13 Correct 349 ms 56104 KB Output is correct
14 Correct 227 ms 55880 KB Output is correct
15 Correct 164 ms 55872 KB Output is correct