oj.uz

Submission #868960

# Submission time Handle Problem Language Result Execution time Memory
868960 2023-11-02T15:50:24 Z AlphaMale06 Fountain (eJOI20_fountain) C++14
100 / 100
 249 ms 35328 KB 
#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define mp make_pair
#define F first
#define S second
#define int long long

const int N = 1e5+3;
const int inf=1e9+10;

int p[N][17];
int sz[N][17];

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, q;
    cin >> n>> q;
    pair<int, int> a[n+1];
    for(int i=1; i<= n; i++)cin >> a[i].F >> a[i].S;
    stack<pair<int, int>> st;
    st.push(mp(inf, 0));
    for(int i=n; i>=1; i--){
        while(st.top().F<=a[i].F){
            st.pop();
        }
        p[i][0]=st.top().S;
        sz[i][0]=a[i].S;
        st.push(mp(a[i].F, i));
    }
    for(int j=0; j<17; j++){
        sz[0][j]=inf;
    }
    for(int i=n; i>=1; i--){
        for(int j=1; j<17; j++){
            p[i][j]=p[p[i][j-1]][j-1];
            if(p[i][j]==0){
                sz[i][j]=inf;
            }
            else{
                sz[i][j]=sz[i][j-1]+sz[p[i][j-1]][j-1];
            }
        }
    }
    while(q--){
        int x, val;
        cin >> x >> val;
        int ans=x;
        for(int i=16; i>=0; i--){
            if(sz[ans][i]<val){
                val-=sz[ans][i];
                ans=p[ans][i];
            }
        }
        if(a[ans].S>=val){
            cout << ans << '\n';
        }
        else cout << p[ans][0] << '\n';
    }
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2524 KB Output is correct
5 Correct 1 ms 2648 KB Output is correct
6 Correct 1 ms 2648 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 30344 KB Output is correct
2 Correct 158 ms 32084 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2524 KB Output is correct
5 Correct 1 ms 2648 KB Output is correct
6 Correct 1 ms 2648 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 145 ms 30344 KB Output is correct
9 Correct 158 ms 32084 KB Output is correct
10 Correct 1 ms 2648 KB Output is correct
11 Correct 49 ms 20112 KB Output is correct
12 Correct 249 ms 35328 KB Output is correct
13 Correct 112 ms 33616 KB Output is correct
14 Correct 118 ms 32616 KB Output is correct
15 Correct 77 ms 32848 KB Output is correct