Submission #1024082

#TimeUsernameProblemLanguageResultExecution timeMemory
1024082vjudge1Osumnjičeni (COCI21_osumnjiceni)C++17
110 / 110
585 ms31184 KiB
// Time: 15-07-2024 16:33:04
// Problem: E - Osumnjičeni
// Contest: Virtual Judge - COCI 2021 Contest # 2
// URL: https://vjudge.net/contest/640690#problem/E
// Memory Limit: 512 MB
// Time Limit: 1000 ms

#include <bits/stdc++.h>

using namespace std;

bool valid(multiset<pair<int,int>> &se,pair<int,int> p)
{
	auto it=se.insert(p);
	if (it!=se.begin())
	{
		it--;
		if ((*it).second>=p.first)
		{
			se.erase(++it);
			return 0;
		}
		it++;
	}
	it++;
	if (it!=se.end())
	{
		if ((*it).first<=p.second)
		{
			se.erase(--it);
			return 0;
		}
	}
	return 1;
}

int main()
{
	int n;
	cin>>n;
	vector<pair<int,int>> vec;
	for (int i=0;i<n;i++)
	{
		int l,r;
		cin>>l>>r;
		vec.push_back({l,r});
	}
	multiset<pair<int,int>> se;
	int i=0,j=0;
	int rc[n+1][18];
	while (i<n)
	{
		if (j<n)
		{
			while (j<n && valid(se,vec[j]))
				j++;
		}
		rc[i][0]=j;
		se.erase(se.find(vec[i]));
		i++;
	}
	for (int i=0;i<18;i++)
		rc[n][i]=n;
	for (int p=1;p<18;p++)
		for (int i=0;i<n;i++)
			rc[i][p]=rc[rc[i][p-1]][p-1];
	int q;
	cin>>q;
	while (q--)
	{
		int a,b;
		cin>>a>>b;
		a--,b--;
		int ans=1;
		for (int p=17;p>=0;p--)
			if (rc[a][p]<=b)
				ans+=(1<<p),a=rc[a][p];
		cout<<ans<<'\n';
	}
	
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...