oj.uz

Submission #631841

# Submission time Handle Problem Language Result Execution time Memory
631841 2022-08-19T00:20:57 Z CyberCow Fountain (eJOI20_fountain) C++17
100 / 100
 312 ms 46696 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <string>
#include <cmath>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <fstream>
#include <iomanip>
#include <iterator>
#include <stack>
#include <deque>
using namespace std;
using ll = long long;
ll d[100005], ch[100005];
stack<int> s;
pair<int, ll> p[100005][25];

void solve()
{
	int n, i, j, q;
	ll x, y;
	cin >> n >> q;
	for ( i = 1; i <= n; i++)
	{
		cin >> d[i] >> ch[i];
	}
	for ( i = n; i > 0; i--)
	{
		while (!s.empty() && d[s.top()] <= d[i])
		{
			s.pop();
		}
		if (!s.empty())
		{
			p[i][0].first = s.top();
			p[i][0].second = ch[s.top()];
		}
		s.push(i);
	}
	for ( i = 1; i <= 20; i++)
	{
		for ( j = 1; j <= n; j++)
		{
			p[j][i].first = p[p[j][i - 1].first][i - 1].first;
			p[j][i].second = p[j][i - 1].second + p[p[j][i - 1].first][i - 1].second;
		}
	}
	for ( i = 0; i < q; i++)
	{
		cin >> x >> y;
		if (ch[x] >= y)
		{
			cout << x << '\n';
			continue;
		}
		y -= ch[x];
		int ans = x;
		for ( j = 20; j > 0; j--)
		{
			if (p[ans][j - 1].second < y)
			{
				y -= p[ans][j - 1].second;
				ans = p[ans][j - 1].first;
			}
		}
		cout << p[ans][0].first << '\n';
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int tt = 1;
	//cin >> tt;
	while (tt--)
	{
		solve();
	}
	return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 1 ms 724 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 43048 KB Output is correct
2 Correct 243 ms 40112 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 202 ms 43048 KB Output is correct
9 Correct 243 ms 40112 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 78 ms 25172 KB Output is correct
12 Correct 312 ms 46696 KB Output is correct
13 Correct 220 ms 45792 KB Output is correct
14 Correct 138 ms 45120 KB Output is correct
15 Correct 118 ms 45304 KB Output is correct