oj.uz

답안 #574205

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
574205 2022-06-08T07:32:56 Z kshitij_sodani Event Hopping (BOI22_events) C++14
10 / 100
 123 ms 12508 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){
		while(cur.size()){
			if((*cur.begin()).a<j.a){
				cur.erase(cur.begin());
			}
			else{
				break;
			}
		}
		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()){
				assert(cur.size()==1);
				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(aa[r]<=bb[cur] and bb[r]>=bb[cur]){
 				su++;
 				break;
 			}
 			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
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 101 ms 11904 KB Output is correct
3 Correct 99 ms 11972 KB Output is correct
4 Correct 121 ms 11920 KB Output is correct
5 Correct 99 ms 12036 KB Output is correct
6 Correct 110 ms 12032 KB Output is correct
7 Correct 102 ms 12080 KB Output is correct
8 Correct 84 ms 12508 KB Output is correct
9 Correct 91 ms 12424 KB Output is correct
10 Correct 118 ms 12288 KB Output is correct
11 Correct 122 ms 12372 KB Output is correct
12 Correct 70 ms 12444 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 106 ms 11996 KB Output is correct
2 Correct 103 ms 11936 KB Output is correct
3 Correct 123 ms 11892 KB Output is correct
4 Correct 85 ms 12436 KB Output is correct
5 Correct 105 ms 12344 KB Output is correct
6 Runtime error 41 ms 7048 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 101 ms 11904 KB Output is correct
3 Correct 99 ms 11972 KB Output is correct
4 Correct 121 ms 11920 KB Output is correct
5 Correct 99 ms 12036 KB Output is correct
6 Correct 110 ms 12032 KB Output is correct
7 Correct 102 ms 12080 KB Output is correct
8 Correct 84 ms 12508 KB Output is correct
9 Correct 91 ms 12424 KB Output is correct
10 Correct 118 ms 12288 KB Output is correct
11 Correct 122 ms 12372 KB Output is correct
12 Correct 70 ms 12444 KB Output is correct
13 Runtime error 1 ms 468 KB Execution killed with signal 6
14 Halted 0 ms 0 KB -