oj.uz

Submission #574196

# Submission time Handle Problem Language Result Execution time Memory
574196 2022-06-08T07:22:26 Z kshitij_sodani Event Hopping (BOI22_events) C++14
10 / 100
 1500 ms 20036 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 2768 KB Output is correct
2 Correct 118 ms 20024 KB Output is correct
3 Execution timed out 1579 ms 19924 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 3 ms 2772 KB Output is correct
4 Correct 12 ms 2772 KB Output is correct
5 Correct 11 ms 2828 KB Output is correct
6 Correct 13 ms 2856 KB Output is correct
7 Correct 15 ms 2772 KB Output is correct
8 Correct 11 ms 2772 KB Output is correct
9 Correct 2 ms 2772 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 3 ms 2772 KB Output is correct
4 Correct 12 ms 2772 KB Output is correct
5 Correct 11 ms 2828 KB Output is correct
6 Correct 13 ms 2856 KB Output is correct
7 Correct 15 ms 2772 KB Output is correct
8 Correct 11 ms 2772 KB Output is correct
9 Correct 2 ms 2772 KB Output is correct
10 Correct 1 ms 2644 KB Output is correct
11 Correct 1 ms 2644 KB Output is correct
12 Correct 3 ms 2772 KB Output is correct
13 Correct 10 ms 2772 KB Output is correct
14 Correct 10 ms 2848 KB Output is correct
15 Correct 18 ms 2852 KB Output is correct
16 Correct 12 ms 2772 KB Output is correct
17 Correct 11 ms 2772 KB Output is correct
18 Correct 3 ms 2772 KB Output is correct
19 Correct 412 ms 5348 KB Output is correct
20 Correct 331 ms 5344 KB Output is correct
21 Execution timed out 1591 ms 5000 KB Time limit exceeded
22 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 1 ms 2644 KB Output is correct
3 Correct 3 ms 2772 KB Output is correct
4 Correct 12 ms 2772 KB Output is correct
5 Correct 11 ms 2828 KB Output is correct
6 Correct 13 ms 2856 KB Output is correct
7 Correct 15 ms 2772 KB Output is correct
8 Correct 11 ms 2772 KB Output is correct
9 Correct 2 ms 2772 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 4 ms 2772 KB Output is correct
13 Correct 10 ms 2856 KB Output is correct
14 Correct 14 ms 2772 KB Output is correct
15 Correct 13 ms 2772 KB Output is correct
16 Correct 19 ms 2772 KB Output is correct
17 Correct 10 ms 2772 KB Output is correct
18 Correct 3 ms 2772 KB Output is correct
19 Correct 463 ms 18208 KB Output is correct
20 Execution timed out 1545 ms 18152 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 20036 KB Output is correct
2 Execution timed out 1580 ms 19820 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 2768 KB Output is correct
2 Correct 118 ms 20024 KB Output is correct
3 Execution timed out 1579 ms 19924 KB Time limit exceeded
4 Halted 0 ms 0 KB -