oj.uz

Submission #704606

# Submission time Handle Problem Language Result Execution time Memory
704606 2023-03-02T11:59:14 Z thrasherr_1 Fountain (eJOI20_fountain) C++17
100 / 100
 295 ms 47788 KB 
#include <bits/stdc++.h>
using namespace std ;

#define ff first
#define ss second
#define ll long long
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define ones(x) __builtin_popcount(x)
#define remove(v)  v.erase(unique(all(v)), v.end())
#define rep(i, a, b) for(int i = a; i <= b; i++)
#define per(i, a, b) for(int i = a; i >= b; i--)

#ifdef local
#include "C:\debug.h"
#else
#define dbg(x...) 42
#endif

#define int ll

const int N = 1e5 + 2 ;

int n , q , d[N] , c[N] , up[N][19] , sum[N][19] , used[N] ;
vector<int> g[N] ;

void dfs(int v , int p) {
    used[v] = 1 ;
    rep(i , 1 , 18) {
        up[v][i] = up[up[v][i - 1]][i - 1] ;
        sum[v][i] = sum[v][i - 1] + sum[up[v][i - 1]][i - 1] ;
    }
    for(auto & to : g[v]) {
        if(to != p) {
            dfs(to , v) ;
        }
    }
}

void solve(){
    cin >> n >> q ;
    rep(i , 1 , n) {
        cin >> d[i] >> c[i] ;
    }
    stack<pair<int,int>> s ;
    rep(i , 1 , n) {
        sum[i][0] = c[i] ;
        while(sz(s) && s.top().first < d[i]) {
            up[s.top().second][0] = i ;
            g[i].pb(s.top().second) ;
            s.pop() ;
        }
        s.push({d[i] , i}) ;
    }
    rep(j , 0 , 18) sum[n + 1][j] = INT_MAX ;
    rep(i , 1 , n) if(!up[i][0]) up[i][0] = n + 1 ;
    per(i , n , 1) {
        if(!used[i]) {
            dfs(i , i) ;
        }
    }
    rep(i , 1 , q) {
        int ind , k ; cin >> ind >> k ;
        per(j , 18 , 0) {
            if(k > sum[ind][j]) {
                k -= sum[ind][j] ;
                ind = up[ind][j] ;
            }
        }
        if(ind > n) ind = 0 ;
        cout << ind << "\n" ;
    }
    
}

signed main () {
	ios::sync_with_stdio(false) ;
	cin.tie(0) ;
	int test = 1 ;
	// cin >> test ; 
	for(int i = 1 ; i <= test ; i++) {
		solve() ;
	}
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2772 KB Output is correct
3 Correct 2 ms 2900 KB Output is correct
4 Correct 2 ms 3028 KB Output is correct
5 Correct 3 ms 3072 KB Output is correct
6 Correct 2 ms 3028 KB Output is correct
7 Correct 3 ms 2940 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 41312 KB Output is correct
2 Correct 223 ms 38416 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2772 KB Output is correct
3 Correct 2 ms 2900 KB Output is correct
4 Correct 2 ms 3028 KB Output is correct
5 Correct 3 ms 3072 KB Output is correct
6 Correct 2 ms 3028 KB Output is correct
7 Correct 3 ms 2940 KB Output is correct
8 Correct 200 ms 41312 KB Output is correct
9 Correct 223 ms 38416 KB Output is correct
10 Correct 3 ms 3080 KB Output is correct
11 Correct 87 ms 24520 KB Output is correct
12 Correct 295 ms 47788 KB Output is correct
13 Correct 210 ms 42540 KB Output is correct
14 Correct 141 ms 40940 KB Output is correct
15 Correct 116 ms 41212 KB Output is correct