oj.uz

Submission #574202

# Submission time Handle Problem Language Result Execution time Memory
574202 2022-06-08T07:29:22 Z kshitij_sodani Event Hopping (BOI22_events) C++14
0 / 100
 178 ms 17192 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;
			cur.erase({bb[j.b.b],j.b.b});
			if(cur.size()){
				auto jj=cur.end();
				jj--;
				if((*jj).a>j.a){
					int no=(*jj).b;
					if(no==j.b.b){
						continue;
					}
					par[j.b.b][0]=no;
				}
			}
			cur.insert({bb[j.b.b],j.b.b});
		}
	}
/*	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];
				}
			}
		}
 		while(true){
 			if(par[cur][0]==-1){
 				su=-1;
 				break;
 			}
 			cur=par[cur][0];
 			su++;
 			if(cur==r){
 				break;
 			}
 			if(aa[r]<=bb[cur] and bb[r]>=bb[cur]){
 				su++;
 				break;
 			}
 			su=-1;
 			break;
 		}
 
 
		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 340 KB Output is correct
2 Correct 138 ms 16556 KB Output is correct
3 Correct 141 ms 16488 KB Output is correct
4 Correct 143 ms 16436 KB Output is correct
5 Correct 157 ms 16616 KB Output is correct
6 Correct 130 ms 16564 KB Output is correct
7 Correct 126 ms 16628 KB Output is correct
8 Correct 135 ms 17044 KB Output is correct
9 Correct 127 ms 17192 KB Output is correct
10 Correct 136 ms 16924 KB Output is correct
11 Incorrect 145 ms 16928 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 212 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 0 ms 340 KB Output is correct
2 Correct 0 ms 212 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 0 ms 340 KB Output is correct
2 Correct 0 ms 212 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
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 16484 KB Output is correct
2 Correct 178 ms 16548 KB Output is correct
3 Correct 160 ms 16532 KB Output is correct
4 Correct 113 ms 17068 KB Output is correct
5 Correct 160 ms 16892 KB Output is correct
6 Incorrect 164 ms 17020 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 138 ms 16556 KB Output is correct
3 Correct 141 ms 16488 KB Output is correct
4 Correct 143 ms 16436 KB Output is correct
5 Correct 157 ms 16616 KB Output is correct
6 Correct 130 ms 16564 KB Output is correct
7 Correct 126 ms 16628 KB Output is correct
8 Correct 135 ms 17044 KB Output is correct
9 Correct 127 ms 17192 KB Output is correct
10 Correct 136 ms 16924 KB Output is correct
11 Incorrect 145 ms 16928 KB Output isn't correct
12 Halted 0 ms 0 KB -