oj.uz

Submission #854671

# Submission time Handle Problem Language Result Execution time Memory
854671 2023-09-28T12:24:06 Z PoPularPlusPlus Event Hopping (BOI22_events) C++17
30 / 100
 111 ms 17352 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define all(x) x.begin(),x.end()
#define vf first 
#define vs second
const int mod = 998244353;

const int MX = 1000000005;
const int L = 20;

struct Seg {
	int siz;
	vector<pair<int,int>> v;

	void init(int n){
		siz = 1;
		while(siz < n)siz *= 2;
		v.assign(siz*2,mp(MX,-1));
	}

	pair<int,int> merge(pair<int,int> x , pair<int,int> y){
		pair<int,int> res;
		res.vf = min(x.vf , y.vf);
		if(x.vf == y.vf)res.vs = min(x.vs , y.vs);
		else if(res.vf == x.vf)res.vs = x.vs;
		else res.vs = y.vs;
		return res;
	}

	void set(int i , pair<int,int> p , int x , int lx , int rx){
		if(rx - lx == 1){
			v[x] = merge(p,v[x]);
			return;
		}
		int m = (lx + rx)/2;
		if(i < m)
			set(i , p , 2 * x + 1 , lx , m);
		else 
			set(i , p , 2 * x + 2 , m , rx);
		v[x] = merge(v[2 * x + 1] , v[2 * x + 2]);
	}

	void set(int i , pair<int,int> p){
		set(i , p , 0 , 0 , siz);
	}

	pair<int,int> range_mx(int l , int r , int x , int lx , int rx){
		if(l >= rx || lx >= r)return mp(MX,-1);
		if(lx >= l && rx <= r)return v[x];
		int m = (lx + rx)/2;
		return merge(range_mx(l,r,2*x+1,lx,m),range_mx(l,r,2*x+2,m,rx));
	}

	pair<int,int> range_mx(int l , int r){
		return range_mx(l , r , 0 , 0 , siz);
	}
};

void solve(){
	int n , q;
	cin >> n >> q;
	vector<pair<int,int>> v(n);
	for(int i = 0; i < n; i++){
		cin >> v[i].vf >> v[i].vs;
	}

	// positions acocrding to sorted e

	vector<pair<int,pair<int,int>>> e_sort;
	//vector<pair<int,pair<int,int>>> rev;

	for(int i = 0; i < n; i++){
		e_sort.pb(mp(v[i].vs , mp(v[i].vf,i)));
	}
	sort(all(e_sort));
	//rev = e_sort;
	//reverse(all(rev));
	int pos[n];
	for(int i = 0; i < n; i++){
		pos[e_sort[i].vs.vs] = i;
	}

	// segtree 

	Seg st;
	st.init(n + 1);
	for(int i = n - 1; i >= 0; i--){
		st.set(i,mp(e_sort[i].vs.vf , i));
	}

	// binary lifting

	int up[n][L];
	int p[n];
	for(int i = 0; i < n; i++){
		pair<int,pair<int,int>> tp = mp(e_sort[i].vs.vf , mp(-1 , -1));
		int left = (lower_bound(all(e_sort),tp) - e_sort.begin());
		if(left == i)
			up[i][0] = p[i] = i;
		else {
			p[i] = st.range_mx(left,i).vs;
			//cout << left << ' ' << st.range_mx(left,i).vf << ' ' << p[i] << '\n';
			up[i][0] = left;
		}
	}
	for(int j = 1; j < L; j++){
		for(int i = 0; i < n; i++){
			if(j == 1)
				up[i][j] = up[p[i]][j-1];
			else 
				up[i][j] = up[up[i][j-1]][j-1];
		}
	}

	// answering the queries 

	while(q--){
		int s , e;
		cin >> s >> e;
		s--;
		e--;
		if(s == e){
			cout << 0 << '\n';
			continue;
		}
		int ogs = pos[s]  , oge = pos[e];
		if(ogs > oge){
			if(v[s].vs >= v[e].vf && v[s].vs <= v[e].vs){
				cout << 1 << '\n';
				continue;
			}
			else {
				cout << "impossible\n";
				continue;
			}
		}
		int i = oge;
		int ans = 0;
		for(int j = L-1; j >= 0; j--){
			if(up[i][j] > ogs){
				ans += (1<<j);
				i = up[i][j];
			}
		}
		if(i > ogs){
			i = up[i][0];
			ans++;
		}
		if(i > ogs)
			cout << "impossible\n";
		else 
			cout << ans << "\n";
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	//int t;cin >> t;
	//while(t--)
		solve();
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 78 ms 16768 KB Output is correct
3 Correct 78 ms 16840 KB Output is correct
4 Correct 91 ms 16836 KB Output is correct
5 Correct 85 ms 16812 KB Output is correct
6 Correct 79 ms 16968 KB Output is correct
7 Correct 77 ms 17016 KB Output is correct
8 Correct 77 ms 17352 KB Output is correct
9 Correct 69 ms 17348 KB Output is correct
10 Correct 82 ms 17096 KB Output is correct
11 Correct 78 ms 17260 KB Output is correct
12 Correct 62 ms 16584 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Incorrect 1 ms 616 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Incorrect 1 ms 616 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Incorrect 1 ms 616 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 77 ms 16688 KB Output is correct
2 Correct 78 ms 16728 KB Output is correct
3 Correct 82 ms 16824 KB Output is correct
4 Correct 67 ms 17348 KB Output is correct
5 Correct 89 ms 17092 KB Output is correct
6 Correct 111 ms 16836 KB Output is correct
7 Correct 93 ms 16832 KB Output is correct
8 Correct 81 ms 17128 KB Output is correct
9 Correct 49 ms 15132 KB Output is correct
10 Correct 81 ms 16584 KB Output is correct
11 Correct 90 ms 16316 KB Output is correct
12 Correct 86 ms 16584 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 78 ms 16768 KB Output is correct
3 Correct 78 ms 16840 KB Output is correct
4 Correct 91 ms 16836 KB Output is correct
5 Correct 85 ms 16812 KB Output is correct
6 Correct 79 ms 16968 KB Output is correct
7 Correct 77 ms 17016 KB Output is correct
8 Correct 77 ms 17352 KB Output is correct
9 Correct 69 ms 17348 KB Output is correct
10 Correct 82 ms 17096 KB Output is correct
11 Correct 78 ms 17260 KB Output is correct
12 Correct 62 ms 16584 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 1 ms 604 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Incorrect 1 ms 616 KB Output isn't correct
19 Halted 0 ms 0 KB -