oj.uz

Submission #574194

# Submission time Handle Problem Language Result Execution time Memory
574194 2022-06-08T07:20:36 Z kshitij_sodani Event Hopping (BOI22_events) C++14
0 / 100
 1500 ms 20044 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 ans[100001];
vector<pair<int,int>> pre[100001];
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());
	
/*	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(bb[r]<bb[l]){
			cout<<"impossible"<<endl;
			continue;
		}
		if(l==r){
			cout<<0<<endl;
			continue;
		}
		pair<int,int> cur={bb[l],l};
		int su=0;

		while(true){
			pair<int,int> ma={-1,-1};
			for(int j=0;j<n;j++){
				if(j==cur.b){
					continue;
				}
				if(aa[j]<=cur.a and bb[j]>=cur.a){
					if(bb[j]<=bb[r]){
						if(cur.a==bb[j] and j!=r){
							continue;
						}
						if(bb[j]>ma.a){
							ma={bb[j],j};
						}
						else if(bb[j]==ma.a){
							if(j==r){
								ma.b=j;
							}
						}
					}
				}
			}
			su++;
			
			if(ma.b==r){
				cout<<su<<endl;
				break;
			}
			if(ma.a==-1){
				cout<<"impossible"<<endl;
				break;
			}
			cur=ma;
			
			
		}


		continue;*/
		pre[r].pb({l,ii});
		





	}
	for(int ii=0;ii<n;ii++){
		if(pre[ii].size()){
			set<pair<int,int>> cur;
			for(int i=0;i<n;i++){
				par[i][0]=-1;
			}
			for(auto j:ss){
				if(bb[j.b.b]>bb[ii]){
					continue;
				}
				if(j.b.a==0){
					cur.insert({bb[j.b.b],j.b.b});
				}
				else{
					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 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(auto jj:pre[ii]){
				int r=ii;
				int l=jj.a;
				if(l==r){
					ans[jj.b]=0;
					continue;
				}
				if(bb[r]<bb[l]){
					ans[jj.b]=-1;
					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];
					}
					else{
						cur=par[cur][0];
						if(aa[r]<=bb[cur] and bb[r]>=bb[cur]){
							su+=2;
						}
						else{
							su=-1;
						}
					}
				}
				else{
					su=-1;
				}

				ans[jj.b]=su;
			}
		}
	}
	for(int i=0;i<q;i++){
		if(ans[i]==-1){
			cout<<"impossible"<<endl;
		}
		else{
			cout<<ans[i]<<endl;
		}
	}

	






	return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 113 ms 20032 KB Output is correct
3 Execution timed out 1569 ms 19824 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 4 ms 2772 KB Output is correct
4 Correct 9 ms 2772 KB Output is correct
5 Correct 11 ms 2856 KB Output is correct
6 Incorrect 10 ms 2772 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 4 ms 2772 KB Output is correct
4 Correct 9 ms 2772 KB Output is correct
5 Correct 11 ms 2856 KB Output is correct
6 Incorrect 10 ms 2772 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 4 ms 2772 KB Output is correct
4 Correct 9 ms 2772 KB Output is correct
5 Correct 11 ms 2856 KB Output is correct
6 Incorrect 10 ms 2772 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 20044 KB Output is correct
2 Execution timed out 1557 ms 19812 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 113 ms 20032 KB Output is correct
3 Execution timed out 1569 ms 19824 KB Time limit exceeded
4 Halted 0 ms 0 KB -