Submission #1257308

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257308		XXBabaProBerkay	Fountain (eJOI20_fountain)	C++20	100 / 100	319 ms	34120 KiB

fountain

#include <bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define MP make_pair
#define PB push_back

using ll = long long;
using ld = long double;
using pi = pair<int, int>;
using pll = pair<ll, ll>;

template<typename T>
using vec = vector<T>;

template<typename T, int N>
using arr = array<T, N>;

ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }
ll lcm(ll a, ll b) { return a * b / gcd(a, b); }

const int INF = 1e9 + 7;
const int MOD = 998244353;

int N, Q;
vec<int> D, C;
arr<vec<pll>, 20> nxt;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> N >> Q;
	D = C = vec<int>(N + 1);
	fill(nxt.begin(), nxt.end(), vec<pll>(N + 1));
	for (int i = 1; i <= N; i++)
		cin >> D[i] >> C[i];

	stack<int> st;
	for (int i = 1; i <= N; i++)
	{
		while (!st.empty() && D[i] > D[st.top()])
		{
			nxt[0][st.top()] = MP(i, C[st.top()]);
			st.pop();
		}
		st.push(i);
	}

	while (!st.empty())
	{
		nxt[0][st.top()] = MP(0, C[st.top()]);
		st.pop();
	}

	nxt[0][0] = MP(0, 0);

	for (int i = 1; i < 20; i++)
		for (int j = 0; j <= N; j++)
			nxt[i][j] = MP(nxt[i - 1][nxt[i - 1][j].F].F, nxt[i - 1][j].S + nxt[i - 1][nxt[i - 1][j].F].S);

	while (Q--)
	{
		int R, V;
		cin >> R >> V;

		for (int i = 19; i >= 0; i--)
			if (nxt[i][R].S < V)
			{
				V -= nxt[i][R].S;
				R = nxt[i][R].F;
			}

		cout << R << '\n';
	}
}

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