oj.uz

Submission #584431

# Submission time Handle Problem Language Result Execution time Memory
584431 2022-06-27T11:32:27 Z Koosha_mv Event Hopping (BOI22_events) C++14
25 / 100
 1500 ms 1680 KB 
#include <bits/stdc++.h>
using namespace std;
#define dbgv(v) cout<<#v<<" = "; f(i,0,v.size()) cout<<v[i]<<" "; cout<<endl
#define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl
#define erorp(x) cout<<#x<<"={"<<x.F<<" , "<<x.S<<"}"<<endl
#define eror(x) cout<<#x<<'='<<(x)<<endl
#define f_(i,a,b) for(int i=a;i>=b;i--)
#define f(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define all(v) v.begin(),v.end()
#define bit(n,k) (((n)>>(k))&1)
#define Add(x,y) x=(x+y)%mod
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define lst(x) x[x.size()-1]
#define sz(x) int(x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first
 
const int N=1e5+99,lg=20;
 
int n,q,s[N],t[N],par[lg][N];
 
int32_t main(){
	ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin>>n>>q;
	f(i,1,n+1){
		cin>>s[i]>>t[i];
		par[0][i]=i;
	}
	f(i,1,n+1){
		f(j,1,n+1){
			if(s[i]<=t[j] && t[j]<=t[i] && s[j]<s[par[0][i]]){
				par[0][i]=j;
			}
		}
	}
	f(i,1,n+1){
		f(l,1,lg){
			par[l][i]=par[l-1][par[l-1][i]];
		}
	}
	while(q--){
		int u,v;
		cin>>u>>v;
		if(u==v){
			cout<<0<<'\n';
			continue ;
		}
		if(s[v]<=t[u]){
			if(t[u]<=t[v]){
				cout<<1<<'\n';
			}
			else{
				cout<<"impossible"<<'\n';
			}
			continue ;
		}
		int ans=1;
		f_(l,lg-1,0){
			if(t[u]<s[par[l][v]]){
				ans+=(1<<l);
				v=par[l][v];
			}
		}
		int p=N;
		while(t[u]<s[v] && p--){
			if(par[0][v]==v) break ;
			v=par[0][v];
			ans++;
		}
		if(s[v]<=t[u]){
			cout<<ans<<'\n';
		}
		else{
			cout<<"impossible"<<'\n';
		}
	}
}
/*
8 1
1 2
3 4
1 5
6 7
5 10
10 20
15 20
999999999 1000000000
1 6
*/

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Execution timed out 1599 ms 1416 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 4 ms 468 KB Output is correct
4 Correct 4 ms 468 KB Output is correct
5 Correct 4 ms 468 KB Output is correct
6 Correct 4 ms 480 KB Output is correct
7 Correct 5 ms 468 KB Output is correct
8 Correct 11 ms 468 KB Output is correct
9 Correct 2 ms 468 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 4 ms 468 KB Output is correct
4 Correct 4 ms 468 KB Output is correct
5 Correct 4 ms 468 KB Output is correct
6 Correct 4 ms 480 KB Output is correct
7 Correct 5 ms 468 KB Output is correct
8 Correct 11 ms 468 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 3 ms 468 KB Output is correct
13 Correct 4 ms 468 KB Output is correct
14 Correct 4 ms 468 KB Output is correct
15 Correct 5 ms 468 KB Output is correct
16 Correct 5 ms 468 KB Output is correct
17 Correct 3 ms 468 KB Output is correct
18 Correct 2 ms 468 KB Output is correct
19 Correct 566 ms 1412 KB Output is correct
20 Correct 1432 ms 1456 KB Output is correct
21 Correct 339 ms 1548 KB Output is correct
22 Correct 107 ms 1680 KB Output is correct
23 Correct 122 ms 1524 KB Output is correct
24 Correct 99 ms 1512 KB Output is correct
25 Correct 127 ms 1252 KB Output is correct

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 4 ms 468 KB Output is correct
4 Correct 4 ms 468 KB Output is correct
5 Correct 4 ms 468 KB Output is correct
6 Correct 4 ms 480 KB Output is correct
7 Correct 5 ms 468 KB Output is correct
8 Correct 11 ms 468 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 4 ms 468 KB Output is correct
13 Correct 4 ms 468 KB Output is correct
14 Correct 3 ms 468 KB Output is correct
15 Correct 4 ms 468 KB Output is correct
16 Correct 4 ms 468 KB Output is correct
17 Correct 5 ms 468 KB Output is correct
18 Correct 2 ms 468 KB Output is correct
19 Execution timed out 1595 ms 1444 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 1588 ms 1492 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Execution timed out 1599 ms 1416 KB Time limit exceeded
3 Halted 0 ms 0 KB -