Submission #812911

#	Time	Username	Problem	Language	Result	Execution time	Memory
812911		OAleksa	Fountain (eJOI20_fountain)	C++14	100 / 100	230 ms	23776 KiB

fountain

#include <bits/stdc++.h>
#define f first
#define s second
using namespace std; 
const int maxn = 1e5 + 69;
const int lg = 18;
int up[maxn][lg], sm[maxn][lg];
vector<int> d(maxn), l(maxn), vis(maxn), g(maxn);
int n, q;

void dfs(int v) {
	if(vis[v])
		return;
	vis[v] = true;
	dfs(g[v]);
	up[v][0] = g[v];
	sm[v][0] = l[g[v]];
	for(int i = 1;i < lg;i++) {
		up[v][i] = up[up[v][i - 1]][i - 1];
		sm[v][i] = sm[v][i - 1] + sm[up[v][i - 1]][i - 1];
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int tt = 1;
	//cin >> tt;
	while(tt--) {
		cin >> n >> q;
		for(int i = 1;i <= n;i++) 
			cin >> d[i] >> l[i];
		l[n + 1] = 1e9;
		vector<pair<int, int>> st;
		st.push_back({1e9 + 69, n + 1});
		for(int i = n; i >= 1; i--) {
			while(!st.empty() && st.back().f <= d[i])
				st.pop_back();
			if(!st.empty()) 
				g[i] = st.back().s;
			st.push_back({d[i], i});
		}
		for(int i = 1;i <= n;i++) 
			if(!vis[i]) 
				dfs(i);
		for(int i = 0;i < q;i++) {
			int v, r;
			cin >> v >> r;
			if(r > l[v]) {
				r -= l[v];
				for(int j = lg - 1;j >= 0;j--) {
					if(sm[v][j] <= r) {
						r -= sm[v][j];
						v = up[v][j];
					}
				}
				if(r > 0)
					v = up[v][0];
			}
			if(v == n + 1)
				v = 0;
			cout << v << "\n";
		}
	}
   return 0;
}

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40