oj.uz

Submission #1119877

# Submission time Handle Problem Language Result Execution time Memory
1119877 2024-11-27T14:24:59 Z thelegendary08 Event Hopping (BOI22_events) C++17
30 / 100
 135 ms 25016 KB 
#include<bits/stdc++.h>
#define pb push_back
#define int long long
#define vi vector<int>
#define vvi vector<vector<int>>
#define pii pair<int, int>
#define vpii vector<pair<int, int>>
#define vc vector<char>
#define vb vector<bool>
#define mii map<int,int>
#define f0r(i,n) for(int i=0;i<n;i++)
#define FOR(i,k,n) for(int i=k;i<n;i++)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define in(a) int a; cin>>a
#define in2(a,b) int a,b; cin>>a>>b
#define in3(a,b,c) int a,b,c; cin>>a>>b>>c
#define in4(a,b,c,d) int a,b,c,d; cin>>a>>b>>c>>d
#define vin(v,n); vi v(n); f0r(i,n){cin>>v[i];}
#define out(a) cout<<a<<'\n'
#define out2(a,b) cout<<a<<' '<<b<<'\n'
#define out3(a,b,c) cout<<a<<' '<<b<<' '<<c<<'\n'
#define out4(a,b,c,d) cout<<a<<' '<<b<<' '<<c<<' '<<d<<'\n'
#define vout(v) cout<<#v<<' '; for(auto u : v){cout<<u<<' ';} cout<<'\n'
#define dout(a) cout<<a<<' '<<#a<<'\n'
#define dout2(a,b) cout<<a<<' '<<#a<<' '<<b<<' '<<#b<<'\n'
#define yn(x); if(x){cout<<"YES"<<'\n';}else{cout<<"NO"<<'\n';}
#define left second
#define right first
const int leg = 1e9 + 7;
const int mod = 998244353;
using namespace std;
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	//ifstream cin(".in");
	//ofstream cout(".out");
	in2(n,q);
	vector<pair<pii,int>> v;
	f0r(i,n){
		in2(a,b);
		v.pb({{b,a},i});
	}
	sort(rall(v));
	vi dex(n);
	f0r(i,n)dex[v[i].second] = i;
	f0r(i,n){
		//out2(v[i].first.first, v[i].first.second);
	}
	vi nxt(n);
	
	f0r(i,n){
		int l = i;
		int r = n-1;
		while(l < r){
			int mid = l + (r - l + 1)/2;
			if(v[i].right.left <= v[mid].right.right){
				l = mid;
			}
			else{
				r = mid - 1;
			}
		}
		
		if(l != i){
			nxt[i] = l;
		}
		else{
			nxt[i] = -1;
		}
	}
	//vout(nxt);
	vvi jmp(n, vi(17));
	f0r(i,n){
		jmp[i][0] = nxt[i];
	}
	FOR(i, 1, 17){
		f0r(j, n){
			if(jmp[j][i-1] == -1)jmp[j][i] = -1;
			else jmp[j][i] = jmp[jmp[j][i-1]][i-1];
		}
	}

	//vout(jmp[0]);
	f0r(i,n){
		//cout<<jmp[i][0]<<' ';
	}
	//out("");
	f0r(i, q){
		in2(a, b);
		if(a == b)out(0);
		else{
			a--;
			b--;
			swap(a,b);
			a = dex[a];
			b = dex[b];
			int goal = v[b].right.right;
			if(v[a].first.left <= goal && goal <= v[a].first.right){
				out(1);
			}
			else{
				//out3(a,b,goal);
				int cnt = 0;
				for(int i = 16; i>=0; i--){
					if(jmp[a][i] != -1){
						if(v[jmp[a][i]].right.left > goal){
							//out("HI");
							cnt += (1 << i);
							a = jmp[a][i];
						}
					}
				}
				
				if(nxt[a] == -1 || !(v[nxt[a]].right.left <= goal && goal <= v[nxt[a]].right.right))out("impossible");
				else out(cnt+2);
			}
			
		}
		
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 82 ms 24556 KB Output is correct
3 Correct 75 ms 24508 KB Output is correct
4 Correct 98 ms 24476 KB Output is correct
5 Correct 135 ms 24380 KB Output is correct
6 Correct 93 ms 24512 KB Output is correct
7 Correct 71 ms 24508 KB Output is correct
8 Correct 64 ms 24920 KB Output is correct
9 Correct 62 ms 24784 KB Output is correct
10 Correct 134 ms 24712 KB Output is correct
11 Correct 110 ms 24868 KB Output is correct
12 Correct 64 ms 24252 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 504 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Incorrect 1 ms 596 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 504 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Incorrect 1 ms 596 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 504 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Incorrect 1 ms 596 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 24516 KB Output is correct
2 Correct 71 ms 24504 KB Output is correct
3 Correct 82 ms 24440 KB Output is correct
4 Correct 63 ms 24764 KB Output is correct
5 Correct 126 ms 25016 KB Output is correct
6 Correct 120 ms 24516 KB Output is correct
7 Correct 106 ms 24456 KB Output is correct
8 Correct 105 ms 24760 KB Output is correct
9 Correct 48 ms 22716 KB Output is correct
10 Correct 70 ms 24196 KB Output is correct
11 Correct 86 ms 23992 KB Output is correct
12 Correct 70 ms 24252 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 82 ms 24556 KB Output is correct
3 Correct 75 ms 24508 KB Output is correct
4 Correct 98 ms 24476 KB Output is correct
5 Correct 135 ms 24380 KB Output is correct
6 Correct 93 ms 24512 KB Output is correct
7 Correct 71 ms 24508 KB Output is correct
8 Correct 64 ms 24920 KB Output is correct
9 Correct 62 ms 24784 KB Output is correct
10 Correct 134 ms 24712 KB Output is correct
11 Correct 110 ms 24868 KB Output is correct
12 Correct 64 ms 24252 KB Output is correct
13 Correct 1 ms 504 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 596 KB Output is correct
16 Correct 2 ms 596 KB Output is correct
17 Correct 1 ms 596 KB Output is correct
18 Incorrect 1 ms 596 KB Output isn't correct
19 Halted 0 ms 0 KB -