Submission #403441

#	Time	Username	Problem	Language	Result	Execution time	Memory
403441		MathMate	Fountain (eJOI20_fountain)	C++17	100 / 100	300 ms	22404 KiB

fountain

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

const int MAX_N = 1e5 + 5;
const int LOG = 20;
const int INF = 1e9 + 5;

struct Element
{
	int wartosc, indeks;
};

vector <int> dlugosci(MAX_N);

int up[MAX_N][LOG];
int sumy_pojemnosci[MAX_N][LOG];

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int n, t;
	cin >> n >> t;

	for(int i = 0; i < n; i++)
	{
		cin >> dlugosci[i] >> sumy_pojemnosci[i][0];
	}

	dlugosci[n] = INF;
	sumy_pojemnosci[n][0] = INF;
	up[n][0] = n;

	stack <Element> kolejna_monotoniczna;

	kolejna_monotoniczna.push({dlugosci[n], n});

	for(int i = n - 1; i >= 0; i--)
	{
		while(kolejna_monotoniczna.top().wartosc <= dlugosci[i])
		{
			kolejna_monotoniczna.pop();
		}

		up[i][0] = kolejna_monotoniczna.top().indeks;

		kolejna_monotoniczna.push({dlugosci[i], i});
	}

	for(int i = 1; i < LOG; i++)
	{
		for(int j = 0; j < n; j++)
		{
			up[j][i] = up[up[j][i - 1]][i - 1];
			sumy_pojemnosci[j][i] = min(sumy_pojemnosci[j][i - 1] + sumy_pojemnosci[up[j][i - 1]][i - 1], INF);
		}
	}

	for(int i = 0; i < t; i++)
	{
		Element zapytanie;
		cin >> zapytanie.indeks >> zapytanie.wartosc;

		zapytanie.indeks--;

		for(int j = LOG - 1; j >= 0; j--)
		{
			if(zapytanie.wartosc > sumy_pojemnosci[zapytanie.indeks][j])
			{
				zapytanie.wartosc -= sumy_pojemnosci[zapytanie.indeks][j];

				zapytanie.indeks = up[zapytanie.indeks][j];
			}
		}

		cout << (zapytanie.indeks + 1) % (n + 1) << "\n";
	}

	return 0;
}

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