Submission #828981

#	Time	Username	Problem	Language	Result	Execution time	Memory
828981		QwertyPi	Event Hopping (BOI22_events)	C++14	100 / 100	912 ms	187712 KiB

events

#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
#define int long long

using namespace std;

const int N = 2e5 + 11;
struct event{
	int s, e, i;
};

event a[N];
int p[N], R[N];
int lift[N][20];
int l2[N][20];
int n, q; 

struct SegTree{
	int t[N << 2];
	void update(int p, int val, int v = 0, int l = 0, int r = n * 2){
		if(l == r) t[v] = min(t[v], val);
		else {
			int m = (l + r) / 2;
			if(p <= m) update(p, val, v * 2 + 1, l, m);
			else update(p, val, v * 2 + 2, m + 1, r);
			t[v] = min(t[v * 2 + 1], t[v * 2 + 2]);
		}
	}
	int query_suff_min(int p, int v = 0, int l = 0, int r = n * 2){
		if(l == r) return t[v];
		int m = (l + r) / 2;
		if(p <= m) return min(query_suff_min(p, v * 2 + 1, l, m), t[v * 2 + 2]);
		else return query_suff_min(p, v * 2 + 2, m + 1, r);
	}
} ST[20];

struct query{
	int u, v, t;
};

int ans[N];

int32_t main(){
	for(int i = 0; i < 20; i++)
		fill(ST[i].t, ST[i].t + (N << 2), 1 << 30);
	cin >> n >> q;
	for(int i = 1; i <= n; i++){
		int s, e; cin >> s >> e; a[i] = {s, e, i};
	}
	{
		set<int> S; map<int, int> mp;
		for(int i = 1; i <= n; i++) S.insert(a[i].s), S.insert(a[i].e);
		int id = 1; for(auto i : S) mp[i] = id++;
		for(int i = 1; i <= n; i++) a[i].s = mp[a[i].s], a[i].e = mp[a[i].e];
	}
	sort(a + 1, a + n + 1, [](event u, event v){ return u.e < v.e; });
	R[n] = n; for(int i = n - 1; i >= 1; i--) R[i] = a[i].e == a[i + 1].e ? R[i + 1] : i;
	for(int i = 1; i <= n; i++) p[a[i].i] = i;

	vector<query> Q;
	for(int i = 0; i < q; i++){
		int u, v; cin >> u >> v; u = p[u], v = p[v];
		Q.push_back({u, v, i});
	}
	sort(Q.begin(), Q.end(), [](query a, query b){ return a.v < b.v; }); int qi = 0;
	for(int i = 1; i <= n; i++){
		for(int j = R[i - 1] + 1; j <= R[i]; j++) ST[0].update(a[j].e, a[j].s);
		lift[a[i].s][0] = ST[0].query_suff_min(a[i].s);
		for(int j = 1; j < 20; j++) {
			ST[j - 1].update(a[i].s, lift[a[i].s][j - 1]);
			lift[a[i].s][j] = ST[j - 1].query_suff_min(lift[a[i].s][j - 1]);
		}
		while(qi < Q.size() && Q[qi].v == i){
			int u = Q[qi].u, v = Q[qi].v, t = Q[qi].t;
			if(a[u].e > a[v].e) ans[t] = -1;
			else if(u == v) ans[t] = 0;
			else if(a[v].s <= a[u].e && a[u].e <= a[v].e) ans[t] = 1;
			else {
				ans[t] = 2;
				int x = a[v].s;
				for(int j = 19; j >= 0; j--){
					if(a[u].e < lift[x][j]) ans[t] += (1 << j), x = lift[x][j];
				}
			}
			qi++;
		}
	}

	for(int i = 0; i < q; i++){
		cout << (ans[i] == -1 || ans[i] > N ? "impossible" : to_string(ans[i])) << '\n';
	}
}

Compilation message (stderr)

events.cpp: In function 'int32_t main()':
events.cpp:74:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |   while(qi < Q.size() && Q[qi].v == i){
      |         ~~~^~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 30 / 30