Submission #548295

#	Time	Username	Problem	Language	Result	Execution time	Memory
548295		aryan12	Osumnjičeni (COCI21_osumnjiceni)	C++17	110 / 110	405 ms	54728 KiB

Main

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

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

const int N = 2e5 + 5;
int DP[20][N];

void Solve() 
{
	int n;
	cin >> n;
	vector<int> max_left(n + 1, 0);
	vector<int> l(n + 1), r(n + 1);
	multiset<pair<int, int> > s;
	for(int i = 1; i <= n; i++)
	{
		cin >> l[i] >> r[i];
	}
	int left = n + 1;
	for(int right = n; right > 0; right--)
	{
		while(left > 1)
		{
			s.insert(make_pair(l[left - 1], r[left - 1]));
			auto idx = s.lower_bound(make_pair(l[left - 1], r[left - 1]));
			// cout << "right = " << right << " no. of elements = " << s.size() << "\n";
			// if(idx == s.begin())
			// {
			// 	cout << "in the beginning\n";
			// }
			// if(next(idx) == s.end())
			// {
			// 	cout << "in the end\n";
			// }
			if(idx != s.begin() && prev(idx)->second >= l[left - 1])
			{
				s.erase(s.find(make_pair(l[left - 1], r[left - 1])));
				break;
			}
			if(next(idx) != s.end() && next(idx)->first <= r[left - 1])
			{
				s.erase(s.find(make_pair(l[left - 1], r[left - 1])));
				break;
			}
			left--;
		}
		max_left[right] = left - 1;
		s.erase(s.find(make_pair(l[right], r[right])));
	}

	for(int i = 1; i <= n; i++)
	{
		// cout << max_left[i] << "\n";
		DP[0][i] = max_left[i];
	}
	// cout << "\n";
	for(int i = 1; i < 20; i++)
	{
		for(int j = 1; j <= n; j++)
		{
			if(DP[i - 1][j] == 0)
			{
				DP[i][j] = 0;
			}
			else
			{
				DP[i][j] = DP[i - 1][DP[i - 1][j]];
			}
		}
	}
	int queries;
	cin >> queries;
	while(queries--)
	{
		int right;
		cin >> left >> right;
		int ans = 0;
		int cur_idx = right;
		for(int i = 19; i >= 0; i--)
		{
			if(DP[i][cur_idx] >= left)
			{
				cur_idx = DP[i][cur_idx];
				ans += (1 << i);
			}
		}
		cout << ans + 1 << "\n";
	}
}

int32_t main() 
{
	auto begin = std::chrono::high_resolution_clock::now();
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;
	// cin >> t;
	for(int i = 1; i <= t; i++) 
	{
		//cout << "Case #" << i << ": ";
		Solve();
	}
	auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 50 / 50