oj.uz

Submission #730717

# Submission time Handle Problem Language Result Execution time Memory
730717 2023-04-26T10:28:17 Z murad_2005 Fountain (eJOI20_fountain) C++14
100 / 100
 365 ms 20360 KB 
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define pii pair<int, int>
#define piii pair<int, pii>
#define pllll pair<ll, ll>
#define plli pair<ll, int>
#define vi vector<int>
#define vvi vector<vector<int>>
#define pb push_back
#define pf push_front
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define size(v) v.size()
#define INF 2e9
#define f first
#define s second
#define ln "\n"

using namespace std;

const int up = 1e5 + 3;
const int LOG = 18;

int d[up], c[up];
int parent[LOG][up], volume[LOG][up];

int LCA(int R, int V){
    for(int i = LOG - 1; i >= 0; --i){
        if(volume[i][R] < V){
            V -= volume[i][R];
            R = parent[i][R];
        }
    }
    return R;
}

void solve(){
    int n, q;
    cin >> n >> q;
    for(int i = 1; i <= n; ++i){
        cin >> d[i] >> c[i];
    }
    d[n + 1] = INF;
    stack<int>st;
    for(int i = 1; i <= n + 1; ++i){
        while(!st.empty() && (d[st.top()] < d[i])){
            parent[0][st.top()] = i;
            volume[0][st.top()] = c[st.top()];
            st.pop();
        }
        st.push(i);
    }
    for(int i = 1; i < LOG; ++i){
        for(int v = 1; v <= n; ++v){
            parent[i][v] = parent[i - 1][parent[i - 1][v]];
            volume[i][v] = volume[i - 1][v] + volume[i - 1][parent[i - 1][v]];
        }
    }

    while(q--){
        int R, V;
        cin >> R >> V;
        int res = LCA(R, V);
        cout << (res = (res == n + 1) ? 0 : res) << "\n";
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    t = 1;
    // cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 540 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 15284 KB Output is correct
2 Correct 248 ms 17308 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 540 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 169 ms 15284 KB Output is correct
9 Correct 248 ms 17308 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 73 ms 10924 KB Output is correct
12 Correct 365 ms 20360 KB Output is correct
13 Correct 191 ms 19936 KB Output is correct
14 Correct 132 ms 19304 KB Output is correct
15 Correct 111 ms 19924 KB Output is correct