oj.uz

Submission #589096

# Submission time Handle Problem Language Result Execution time Memory
589096 2022-07-04T09:20:05 Z berr Fountain (eJOI20_fountain) C++17
100 / 100
 647 ms 61236 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--;
        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
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 716 KB Output is correct
4 Correct 2 ms 872 KB Output is correct
5 Correct 3 ms 852 KB Output is correct
6 Correct 3 ms 848 KB Output is correct
7 Correct 1 ms 852 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 404 ms 53996 KB Output is correct
2 Correct 448 ms 49760 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 716 KB Output is correct
4 Correct 2 ms 872 KB Output is correct
5 Correct 3 ms 852 KB Output is correct
6 Correct 3 ms 848 KB Output is correct
7 Correct 1 ms 852 KB Output is correct
8 Correct 404 ms 53996 KB Output is correct
9 Correct 448 ms 49760 KB Output is correct
10 Correct 2 ms 852 KB Output is correct
11 Correct 208 ms 32724 KB Output is correct
12 Correct 647 ms 61236 KB Output is correct
13 Correct 503 ms 59404 KB Output is correct
14 Correct 347 ms 58424 KB Output is correct
15 Correct 228 ms 58708 KB Output is correct