oj.uz

Submission #574198

# Submission time Handle Problem Language Result Execution time Memory
574198 2022-06-08T07:23:56 Z kshitij_sodani Event Hopping (BOI22_events) C++14
20 / 100
 140 ms 17088 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;
					if(no==j.b.b){
						continue;
					}
					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 1 ms 340 KB Output is correct
2 Correct 109 ms 16548 KB Output is correct
3 Correct 110 ms 16540 KB Output is correct
4 Correct 131 ms 16564 KB Output is correct
5 Correct 119 ms 16580 KB Output is correct
6 Correct 110 ms 16636 KB Output is correct
7 Correct 103 ms 16580 KB Output is correct
8 Correct 94 ms 17032 KB Output is correct
9 Correct 98 ms 17080 KB Output is correct
10 Correct 117 ms 16888 KB Output is correct
11 Incorrect 115 ms 16892 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 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 1 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 1 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
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 16520 KB Output is correct
2 Correct 115 ms 16504 KB Output is correct
3 Correct 140 ms 16548 KB Output is correct
4 Correct 97 ms 17088 KB Output is correct
5 Correct 119 ms 16892 KB Output is correct
6 Correct 111 ms 16644 KB Output is correct
7 Correct 116 ms 16692 KB Output is correct
8 Correct 102 ms 16820 KB Output is correct
9 Correct 69 ms 15868 KB Output is correct
10 Correct 104 ms 16348 KB Output is correct
11 Correct 93 ms 16144 KB Output is correct
12 Correct 109 ms 16372 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 109 ms 16548 KB Output is correct
3 Correct 110 ms 16540 KB Output is correct
4 Correct 131 ms 16564 KB Output is correct
5 Correct 119 ms 16580 KB Output is correct
6 Correct 110 ms 16636 KB Output is correct
7 Correct 103 ms 16580 KB Output is correct
8 Correct 94 ms 17032 KB Output is correct
9 Correct 98 ms 17080 KB Output is correct
10 Correct 117 ms 16888 KB Output is correct
11 Incorrect 115 ms 16892 KB Output isn't correct
12 Halted 0 ms 0 KB -