oj.uz

Submission #467948

# Submission time Handle Problem Language Result Execution time Memory
467948 2021-08-25T17:26:27 Z Elias Fountain (eJOI20_fountain) C++17
100 / 100
 400 ms 49336 KB 
//#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 2 ms 588 KB Output is correct
6 Correct 2 ms 588 KB Output is correct
7 Correct 1 ms 588 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 45680 KB Output is correct
2 Correct 293 ms 42680 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 2 ms 588 KB Output is correct
6 Correct 2 ms 588 KB Output is correct
7 Correct 1 ms 588 KB Output is correct
8 Correct 264 ms 45680 KB Output is correct
9 Correct 293 ms 42680 KB Output is correct
10 Correct 1 ms 588 KB Output is correct
11 Correct 131 ms 24488 KB Output is correct
12 Correct 400 ms 49336 KB Output is correct
13 Correct 310 ms 47020 KB Output is correct
14 Correct 207 ms 45968 KB Output is correct
15 Correct 182 ms 46220 KB Output is correct