Submission #467948

#	Time	Username	Problem	Language	Result	Execution time	Memory
467948		Elias	Fountain (eJOI20_fountain)	C++17	100 / 100	400 ms	49336 KiB

fountain

//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>

using namespace std;

#define int long long
const int onenineseven = 1e9 + 7;

int ilog2(int x)
{
	int p = 0;
	while (x >>= 1)
		p++;
	return p;
}

struct Level
{
	int size;
	int capacity;
	int level;
};

signed main()
{
	cin.tie(0);
	ios_base::sync_with_stdio(false);

	int n, q;
	cin >> n >> q;

	int logn = ilog2(n) + 1;

	vector<vector<Level>> parents(logn, vector<Level>(n));

	stack<Level> levels;
	levels.push({LLONG_MAX, -1, -1});

	vector<pair<int, int>> ls(n);

	for (auto &[s, c] : ls)
		cin >> s >> c;

	reverse(ls.begin(), ls.end());

	for (int i = 0; i < n; i++)
	{
		auto [s, c] = ls[i];

		while (levels.top().size <= s)
			levels.pop();

		parents[0][i] = {0, c, levels.top().level};

		levels.push({s, c, i});
	}

	// binary lifting
	for (int k = 1; k < logn; k++)
	{
		for (int i = 0; i < n; i++)
		{
			Level f = parents[k - 1][i];
			if (f.level != -1)
			{
				Level s = parents[k - 1][f.level];
				parents[k][i] = {0, f.capacity + s.capacity, s.level};
			}
			else
				parents[k][i] = f;
		}
	}

	while (q--)
	{
		int s, w;
		cin >> s >> w;
		s = n - s;
		for (int p = logn - 1; p >= 0; p--)
		{
			if (s != -1 && w - parents[p][s].capacity > 0)
			{
				w -= parents[p][s].capacity;
				s = parents[p][s].level;
			}
		}

		if (s == -1)
			cout << "0\n";
		else
		{
			cout << n - (s) << "\n";
		}
	}
}

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