oj.uz

Submission #574192

# Submission time Handle Problem Language Result Execution time Memory
574192 2022-06-08T07:16:09 Z kshitij_sodani Event Hopping (BOI22_events) C++14
10 / 100
 1500 ms 13760 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{
					par[j.b.b][0]=-1;
					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]=-1;
					continue;
				}


				if(su==-1){
					ans[jj.b]=-1;
					continue;
				}
				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 Execution timed out 1585 ms 13752 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 194 ms 2808 KB Output is correct
4 Correct 28 ms 2772 KB Output is correct
5 Correct 45 ms 2896 KB Output is correct
6 Correct 2 ms 2772 KB Output is correct
7 Correct 3 ms 2824 KB Output is correct
8 Correct 2 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 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 194 ms 2808 KB Output is correct
4 Correct 28 ms 2772 KB Output is correct
5 Correct 45 ms 2896 KB Output is correct
6 Correct 2 ms 2772 KB Output is correct
7 Correct 3 ms 2824 KB Output is correct
8 Correct 2 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 188 ms 2808 KB Output is correct
13 Correct 27 ms 2824 KB Output is correct
14 Correct 47 ms 2772 KB Output is correct
15 Correct 4 ms 2772 KB Output is correct
16 Correct 3 ms 2772 KB Output is correct
17 Correct 2 ms 2772 KB Output is correct
18 Correct 2 ms 2772 KB Output is correct
19 Execution timed out 1591 ms 3348 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 194 ms 2808 KB Output is correct
4 Correct 28 ms 2772 KB Output is correct
5 Correct 45 ms 2896 KB Output is correct
6 Correct 2 ms 2772 KB Output is correct
7 Correct 3 ms 2824 KB Output is correct
8 Correct 2 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 207 ms 2808 KB Output is correct
13 Correct 32 ms 2828 KB Output is correct
14 Correct 44 ms 2772 KB Output is correct
15 Correct 2 ms 2772 KB Output is correct
16 Correct 2 ms 2756 KB Output is correct
17 Correct 2 ms 2772 KB Output is correct
18 Correct 2 ms 2772 KB Output is correct
19 Execution timed out 1573 ms 13760 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1583 ms 13752 KB Time limit exceeded
2 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 Execution timed out 1585 ms 13752 KB Time limit exceeded
3 Halted 0 ms 0 KB -