oj.uz

Submission #574185

# Submission time Handle Problem Language Result Execution time Memory
574185 2022-06-08T06:54:17 Z kshitij_sodani Event Hopping (BOI22_events) C++14
20 / 100
 129 ms 17080 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define a first
#define b second
#define pb push_back
#define endl '\n'
int aa[100001];
int bb[100001];
int par[100001][20];
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n,q;
	cin>>n>>q;
	vector<pair<int,pair<int,int>>> ss;
	for(int i=0;i<n;i++){
		cin>>aa[i]>>bb[i];
		ss.pb({aa[i],{0,i}});
		ss.pb({bb[i],{1,i}});
	}
	sort(ss.begin(),ss.end());
	set<pair<int,int>> cur;
	for(auto j:ss){
		if(j.b.a==0){
			cur.insert({bb[j.b.b],j.b.b});
		}
		else{
			par[j.b.b][0]=-1;
			if(cur.size()){
				auto jj=cur.end();
				jj--;
				if((*jj).a>j.a){
					int no=(*jj).b;
					par[j.b.b][0]=no;
				}
			}
		}
	}
/*	for(int i=0;i<n;i++){
		cout<<par[i][0]<<",";
	}
	cout<<endl;*/
	for(int j=1;j<20;j++){
		for(int i=0;i<n;i++){
			if(par[i][j-1]==-1){
				par[i][j]=-1;
			}
			else{
				par[i][j]=par[par[i][j-1]][j-1];
			}
		}
	}
	for(int ii=0;ii<q;ii++){
		int l,r;
		cin>>l>>r;
		l--;
		r--;
		if(l==r){
			cout<<0<<endl;
			continue;
		}
		if(bb[r]<bb[l]){
			cout<<"impossible"<<endl;
			continue;
		}
		int su=0;
		int cur=l;
		for(int j=19;j>=0;j--){
			if(par[cur][j]>=0){
				if(bb[par[cur][j]]<bb[r]){
					su+=(1<<j);
					cur=par[cur][j];
				}
			}
		}

		if(par[cur][0]>=0){
			
			if(aa[r]<=bb[cur] and bb[r]>=bb[cur]){
				su++;
				cur=par[cur][0];
				//cout<<cur<<":"<<bb[cur]<<endl;
			}
			else{
				cur=par[cur][0];
				//cout<<cur<<",,"<<endl;
				//if(par[cur][0]>=0){
					if(aa[r]<=bb[cur] and bb[r]>=bb[cur]){
						su+=2;
					}
					else{
						su=-1;
					}
				//}
				//else{
				//	su=-1;
				//}
			//	if(par[cur][1]>=0)
			}
		}
		else{
			//su=-1;
			cout<<"impossible"<<endl;
			continue;
		}


		if(su==-1){
			cout<<"impossible"<<endl;
			continue;
		}
		cout<<su<<endl;





	}


	






	return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 96 ms 16520 KB Output is correct
3 Correct 101 ms 16516 KB Output is correct
4 Correct 128 ms 16472 KB Output is correct
5 Correct 112 ms 16588 KB Output is correct
6 Correct 109 ms 16572 KB Output is correct
7 Correct 106 ms 16692 KB Output is correct
8 Correct 93 ms 16948 KB Output is correct
9 Correct 96 ms 17080 KB Output is correct
10 Correct 127 ms 16948 KB Output is correct
11 Incorrect 113 ms 16948 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 15.0

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

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 16484 KB Output is correct
2 Correct 100 ms 16508 KB Output is correct
3 Correct 129 ms 16520 KB Output is correct
4 Correct 95 ms 17048 KB Output is correct
5 Correct 129 ms 16912 KB Output is correct
6 Correct 117 ms 16692 KB Output is correct
7 Correct 109 ms 16720 KB Output is correct
8 Correct 104 ms 16780 KB Output is correct
9 Correct 67 ms 15888 KB Output is correct
10 Correct 122 ms 16308 KB Output is correct
11 Correct 96 ms 16068 KB Output is correct
12 Correct 110 ms 16328 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 96 ms 16520 KB Output is correct
3 Correct 101 ms 16516 KB Output is correct
4 Correct 128 ms 16472 KB Output is correct
5 Correct 112 ms 16588 KB Output is correct
6 Correct 109 ms 16572 KB Output is correct
7 Correct 106 ms 16692 KB Output is correct
8 Correct 93 ms 16948 KB Output is correct
9 Correct 96 ms 17080 KB Output is correct
10 Correct 127 ms 16948 KB Output is correct
11 Incorrect 113 ms 16948 KB Output isn't correct
12 Halted 0 ms 0 KB -