oj.uz

Submission #403441

# Submission time Handle Problem Language Result Execution time Memory
403441 2021-05-13T07:41:42 Z MathMate Fountain (eJOI20_fountain) C++17
100 / 100
 300 ms 22404 KB 
#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 1 ms 748 KB Output is correct
3 Correct 2 ms 800 KB Output is correct
4 Correct 2 ms 844 KB Output is correct
5 Correct 3 ms 924 KB Output is correct
6 Correct 2 ms 844 KB Output is correct
7 Correct 2 ms 844 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 20044 KB Output is correct
2 Correct 227 ms 19060 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 1 ms 748 KB Output is correct
3 Correct 2 ms 800 KB Output is correct
4 Correct 2 ms 844 KB Output is correct
5 Correct 3 ms 924 KB Output is correct
6 Correct 2 ms 844 KB Output is correct
7 Correct 2 ms 844 KB Output is correct
8 Correct 205 ms 20044 KB Output is correct
9 Correct 227 ms 19060 KB Output is correct
10 Correct 3 ms 844 KB Output is correct
11 Correct 95 ms 11668 KB Output is correct
12 Correct 300 ms 22404 KB Output is correct
13 Correct 217 ms 21204 KB Output is correct
14 Correct 176 ms 20420 KB Output is correct
15 Correct 152 ms 20736 KB Output is correct