oj.uz

Submission #602660

# Submission time Handle Problem Language Result Execution time Memory
602660 2022-07-23T09:56:17 Z Abdulmohsen1284 Event Hopping (BOI22_events) C++14
0 / 100
 482 ms 57000 KB 
#include <bits/stdc++.h> 
using namespace std;

long long bg[300005],en[300005],pa[100005][35],ope=0,twos[40],inf=1e5+1;

long long fin(long long cur,long long lim)
{
	for(int i=32;i>=0;i--)
	{
		//cout<<ope<<" ";
		if(en[pa[cur][i]]<=en[lim]&&lim!=pa[cur][i])
		{
			if(pa[cur][i]!=cur)
			ope+=twos[i];
			cur=pa[cur][i];
		}
		//cout<<cur<<" ";
	}
	return cur;
}

int main()
{
	twos[0]=1;
	for(int i=1;i<34;i++)
		twos[i]=twos[i-1]*2;
	long long n,q;
	bg[inf]=2e9;
	en[inf]=2e9;
	pa[inf][0]=inf;
	cin>>n>>q;
	set <pair <pair <long long, bool> , long long > > h;
	set <pair <long long, long long > > cur;
	cur.insert({1000000,inf});
	set <long long> bef[100005];
	for(int i=0;i<n;i++)
	{
		bef[i].insert(99999999999);
		pa[i][0]=inf;
		cin>>bg[i]>>en[i];
		h.insert({{bg[i],false},i});
		h.insert({{en[i],true},i});
	}

	for(auto i: h)
	{
		if(i.first.second)
		{	
			cur.erase({i.first.first*-1,i.second});
			auto fg = *cur.begin();
			if(en[fg.second]!=en[i.second])
			pa[i.second][0]=fg.second;
			bef[fg.second].insert(bg[i.second]);
		}
		else
		{
			cur.insert({en[i.second]*-1,i.second});
		}
	}
	for(int i=1;i<33;i++)
	{
		for(int j=0;j<n;j++)
		{
			pa[j][i]=pa[pa[j][i-1]][i-1];
			//cout<<pa[j][i]<<" ";
		}
	}
	for(int i=0;i<q;i++)
	{
		long long fr,sc;
		ope=1;
		cin>>fr>>sc;
		fr--;
		sc--;
		if(fr==sc){
			cout<<"0\n";
			continue;
		}
		long long las=fin(fr,sc);
		if(*bef[sc].begin()<=en[las]&&en[sc]>=en[fr]&&las!=inf)
		{
			cout<<ope<<"\n";
		}
		else{
			las=pa[las][0];
			if(*bef[sc].begin()<=en[las]&&en[sc]>=en[fr])
		{
			cout<<ope+1<<"\n";
		}
		else
			cout<<"impossible\n";
		}
	}
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Incorrect 461 ms 56940 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Incorrect 4 ms 5460 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Incorrect 4 ms 5460 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Incorrect 4 ms 5460 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 482 ms 57000 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Incorrect 461 ms 56940 KB Output isn't correct
3 Halted 0 ms 0 KB -