oj.uz

Submission #482067

# Submission time Handle Problem Language Result Execution time Memory
482067 2021-10-22T23:51:32 Z s_samchenko Fountain (eJOI20_fountain) C++17
100 / 100
 501 ms 102808 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define ll long long
#define ff first
#define ss second
#define int ll
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define pb push_back
#define pii pair <int, int>
using namespace std;
const int inf = 1e15;
const int mod = 1e9+7;
const int N = 2e5+100;

vector <int> a(N), b(N), d(N);
vector < vector <pii> > g(N);
vector < vector <int> > up(N, vector <int> (20)), sum = up;

void dfs(int v, int pr, int h = 0){
	d[v] = h+1;
	up[v][0] = pr;
	for (auto to : g[v]){
		dfs(to.ff, v, h+1);
		sum[to.ff][0] = to.ss;
	}
}

int get(int r, int v){
	for (int j = 19; j >= 0; --j){
		if (sum[r][j] < v){
			v -= sum[r][j];
			r = up[r][j];
		}
	}
	return r;
}

void solve(){
	int n, q;
	cin >> n >> q;
	for (int i = 1; i <= n; ++i) cin >> a[i] >> b[i];
	vector <pii> st; st.pb({inf, 0});
	for (int i = n; i >= 1; --i){
		while (st.back().ff <= a[i]) st.pop_back();
		pii v = st.back();
		g[v.ss].pb({i, b[i]});
		st.pb({a[i], i});
	}
	
	for (int i = 0; i <= n; ++i)
		if (!d[i]) dfs(i, i);
	for (int j = 1; j < 20; ++j)
		for (int i = 0; i <= n; ++i) up[i][j] = up[up[i][j-1]][j-1];
	for (int j = 1; j < 20; ++j)
		for (int i = 0; i <= n; ++i) sum[i][j] = sum[i][j-1] + sum[up[i][j-1]][j-1];
	
	while (q--){
		int r, v;
		cin >> r >> v;
		cout << get(r, v) << '\n';
	}
}

signed main(){
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int tt = 1;
	//cin >> tt;
	while (tt--){
		solve();
		cout << '\n';
	}
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 87992 KB Output is correct
2 Correct 52 ms 87964 KB Output is correct
3 Correct 53 ms 87972 KB Output is correct
4 Correct 53 ms 87988 KB Output is correct
5 Correct 52 ms 88060 KB Output is correct
6 Correct 52 ms 88004 KB Output is correct
7 Correct 57 ms 88036 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 337 ms 97768 KB Output is correct
2 Correct 426 ms 97240 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 87992 KB Output is correct
2 Correct 52 ms 87964 KB Output is correct
3 Correct 53 ms 87972 KB Output is correct
4 Correct 53 ms 87988 KB Output is correct
5 Correct 52 ms 88060 KB Output is correct
6 Correct 52 ms 88004 KB Output is correct
7 Correct 57 ms 88036 KB Output is correct
8 Correct 337 ms 97768 KB Output is correct
9 Correct 426 ms 97240 KB Output is correct
10 Correct 53 ms 87988 KB Output is correct
11 Correct 172 ms 92496 KB Output is correct
12 Correct 501 ms 102808 KB Output is correct
13 Correct 352 ms 96680 KB Output is correct
14 Correct 286 ms 94800 KB Output is correct
15 Correct 221 ms 94264 KB Output is correct