oj.uz

Submission #871042

# Submission time Handle Problem Language Result Execution time Memory
871042 2023-11-09T18:39:52 Z Theo830 Fountain (eJOI20_fountain) C++17
100 / 100
 417 ms 34792 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];
long long 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 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Correct 3 ms 2648 KB Output is correct
5 Correct 3 ms 2652 KB Output is correct
6 Correct 3 ms 2652 KB Output is correct
7 Correct 3 ms 2652 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 33164 KB Output is correct
2 Correct 313 ms 32336 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Correct 3 ms 2648 KB Output is correct
5 Correct 3 ms 2652 KB Output is correct
6 Correct 3 ms 2652 KB Output is correct
7 Correct 3 ms 2652 KB Output is correct
8 Correct 263 ms 33164 KB Output is correct
9 Correct 313 ms 32336 KB Output is correct
10 Correct 3 ms 2648 KB Output is correct
11 Correct 153 ms 19336 KB Output is correct
12 Correct 417 ms 34792 KB Output is correct
13 Correct 337 ms 29776 KB Output is correct
14 Correct 316 ms 29372 KB Output is correct
15 Correct 292 ms 29396 KB Output is correct