Submission #812813

#	Time	Username	Problem	Language	Result	Execution time	Memory
812813		OAleksa	Fountain (eJOI20_fountain)	C++14	0 / 100	106 ms	23928 KiB

fountain

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

void dfs(int v) {
	vis[v] = true;
	if(!g[v].empty()) {
		dfs(g[v].front());
		up[v][0] = g[v].front();
		sm[v][0] = l[g[v].front()];
		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, 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].push_back(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;
			int u = v;
			if(r > l[v]) {
				r -= l[v];
				for(int j = lg - 1;j >= 0;j--) {
					if(sm[u][j] <= r) {
						r -= sm[u][j];
						u = up[u][j];
						if(l[u] >= r)
							break;
						else
							r -= l[u];
					}
				}
				if(r > 0)
					u = up[u][0];
			}
			if(u == n + 1)
				u = 0;
			cout << u << "\n";
		}
	}
   return 0;
}

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