Submission #862681

#	Time	Username	Problem	Language	Result	Execution time	Memory
862681		Cyber_Wolf	Osumnjičeni (COCI21_osumnjiceni)	C++17	0 / 110	113 ms	11288 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define lg long long 

const lg N = 2e5+5;

lg l[N], r[N], anc[N][20], n;

int main()
{
	lg n;
	cin >> n;
	for(int i = 1; i <= n; i++)
	{
		cin >> l[i] >> r[i];
	}
	lg en = 1;
	multiset<array<lg, 2>> se;
	se.insert({l[1], r[1]});
	for(int i = 1; i <= n; i++)
	{
		while(en+1 <= n)
		{
			auto it = se.lower_bound({l[en], l[en]});
			if(it != se.end() && (*it)[0] >= l[en] && (*it)[0] <= r[en])
			{
				break;
			}
			if(it != se.begin())
			{
				it--;
				if((*it)[1] >= l[en] && (*it)[1] <= r[en])
				{
					break;
				}
			}
			se.insert({l[en], r[en]});
			en++;
		}
		anc[i][0] = en;
		se.erase(se.find({l[i], r[i]}));
	}
	for(int i = n; i >= 1; i--)
	{
		for(int j = 1; j < 20; j++)
		{
			anc[i][j] = anc[anc[i][j-1]+1][j-1];
		}
	}
	lg q;
	cin >> q;
	while(q--)
	{
		lg a, b;
		cin >> a >> b;
		lg ans = 0;
		for(int i = 19; i >= 0 && a <= b; i--)
		{
			if(anc[a][i] <= b && anc[a][i])
			{
				ans += (1ll << i);
				a = anc[a][i]+1;
			}
		}
		cout << ans << '\n';
	}
} 

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