oj.uz

Submission #871041

# Submission time Handle Problem Language Result Execution time Memory
871041 2023-11-09T18:38:15 Z Theo830 Fountain (eJOI20_fountain) C++17
100 / 100
 360 ms 31372 KB 
#include <bits/stdc++.h>
using namespace std;
#define ii pair<int,int>
vector<vector<int> >adj;
const int N = 1e5 + 5;
const int K = 18; /// K = log2N
int d[N],c[N];
int lift[N][K];
int sum[N][K];
void dfs(int idx,int p){
    lift[idx][0] = p;
    sum[idx][0] = c[idx];
    for(int j = 1;j < K;j++){
        lift[idx][j] = lift[lift[idx][j-1]][j-1];
        sum[idx][j] = sum[idx][j-1] + sum[lift[idx][j-1]][j-1];
    }
    for(auto x:adj[idx]){
        if(x != p){
            dfs(x,idx);
        }
    }
}
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n,q;
    cin>>n>>q;
    adj.assign(n+5,vector<int>());
    for(int i = 1;i <= n;i++){
        cin>>d[i]>>c[i];
    }
    stack<ii>s;
    for(int i = n;i >= 1;i--){
        while(!s.empty() && s.top().first <= d[i]){
            s.pop();
        }
        if(s.empty()){
            adj[i].push_back(0);
            adj[0].push_back(i);
        }
        else{
            adj[i].push_back(s.top().second);
            adj[s.top().second].push_back(i);
        }
        s.push(ii(d[i],i));
    }
    dfs(0,0);
    while(q--){
        int r,v;
        cin>>r>>v;
        for(int j = K-1;j >= 0;j--){
            if(sum[r][j] < v){
                v -= sum[r][j];
                r = lift[r][j];
            }
        }
        cout<<r<<endl;
    }
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 2 ms 4444 KB Output is correct
3 Correct 3 ms 4444 KB Output is correct
4 Correct 3 ms 4700 KB Output is correct
5 Correct 4 ms 4696 KB Output is correct
6 Correct 4 ms 4700 KB Output is correct
7 Correct 4 ms 4700 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 26448 KB Output is correct
2 Correct 243 ms 25584 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 2 ms 4444 KB Output is correct
3 Correct 3 ms 4444 KB Output is correct
4 Correct 3 ms 4700 KB Output is correct
5 Correct 4 ms 4696 KB Output is correct
6 Correct 4 ms 4700 KB Output is correct
7 Correct 4 ms 4700 KB Output is correct
8 Correct 225 ms 26448 KB Output is correct
9 Correct 243 ms 25584 KB Output is correct
10 Correct 4 ms 4700 KB Output is correct
11 Correct 157 ms 18952 KB Output is correct
12 Correct 360 ms 31372 KB Output is correct
13 Correct 341 ms 26324 KB Output is correct
14 Correct 293 ms 24940 KB Output is correct
15 Correct 312 ms 25664 KB Output is correct