oj.uz

Submission #602646

# Submission time Handle Problem Language Result Execution time Memory
602646 2022-07-23T09:46:45 Z Abdulmohsen1284 Event Hopping (BOI22_events) C++14
10 / 100
 563 ms 60052 KB 
#include <bits/stdc++.h> 
using namespace std;

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

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];
		}
		
	}
	return cur;
}

int main()
{
	twos[0]=1;
	for(int i=1;i<34;i++)
		twos[i]=twos[i-1]*2;
	long long n,q;
	cin>>n>>q;
	set <pair <pair <long long, bool> , long long > > h;
	set <pair <long long, long long > > cur;
	set <long long> bef[100005];
	for(int i=0;i<n;i++)
	{
		bef[i].insert(99999999999);
		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)
		{
			auto fg = *cur.begin();
			pa[i.second][0]=fg.second;
			bef[fg.second].insert(bg[i.second]);
			cur.erase({i.first.first*-1,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])
		{
			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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 422 ms 59536 KB Output is correct
3 Correct 437 ms 59528 KB Output is correct
4 Correct 504 ms 59376 KB Output is correct
5 Correct 454 ms 59596 KB Output is correct
6 Correct 485 ms 59576 KB Output is correct
7 Correct 450 ms 59724 KB Output is correct
8 Correct 426 ms 60052 KB Output is correct
9 Correct 431 ms 59948 KB Output is correct
10 Correct 498 ms 59860 KB Output is correct
11 Correct 502 ms 59884 KB Output is correct
12 Correct 334 ms 59164 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 15.0

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

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 454 ms 59448 KB Output is correct
2 Correct 433 ms 59468 KB Output is correct
3 Correct 525 ms 59376 KB Output is correct
4 Correct 412 ms 59956 KB Output is correct
5 Correct 528 ms 59820 KB Output is correct
6 Correct 563 ms 59600 KB Output is correct
7 Correct 494 ms 59620 KB Output is correct
8 Incorrect 494 ms 59916 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 422 ms 59536 KB Output is correct
3 Correct 437 ms 59528 KB Output is correct
4 Correct 504 ms 59376 KB Output is correct
5 Correct 454 ms 59596 KB Output is correct
6 Correct 485 ms 59576 KB Output is correct
7 Correct 450 ms 59724 KB Output is correct
8 Correct 426 ms 60052 KB Output is correct
9 Correct 431 ms 59948 KB Output is correct
10 Correct 498 ms 59860 KB Output is correct
11 Correct 502 ms 59884 KB Output is correct
12 Correct 334 ms 59164 KB Output is correct
13 Correct 3 ms 4948 KB Output is correct
14 Correct 3 ms 4948 KB Output is correct
15 Correct 5 ms 5460 KB Output is correct
16 Correct 4 ms 5492 KB Output is correct
17 Incorrect 4 ms 5460 KB Output isn't correct
18 Halted 0 ms 0 KB -