Submission #1178585

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178585		kl0989e	Event Hopping (BOI22_events)	C++17	25 / 100	1596 ms	25412 KiB

events

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pi pair<int, int>
#define pl pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(),(x).end()

const int maxn=1e5+10;
const int logg=ceil(log2(maxn));
vector<vi> graph(maxn);
vector<vi> prv(maxn,vi(logg+1));

void dfs(int cur) {
	for (int i=1; i<=logg; i++) {
		prv[cur][i]=prv[prv[cur][i-1]][i-1];
	}
	for (auto to:graph[cur]) {
		dfs(to);
	}
}

struct segTree {
	struct node {
		int ind=-1,val=2e9;

		node(int _ind=-1, int _val=2e9): ind(_ind),val(_val) {}
	};
	node unite(node a, node b) {
		if (a.val<=b.val) {
			return a;
		}
		return b;
	}

	vector<node> seg;
	int sze;

	segTree(int n, vector<pi>& a): sze(n) {
		seg.resize(4*sze);
		build(a,1,0,sze-1);
	}

	void build(vector<pi>& a, int v, int tl, int tr) {
		if (tl==tr) {
			seg[v].val=a[tl].se;
			seg[v].ind=a[tl].fi;
			return;
		}
		int tm=tl+(tr-tl)/2;
		build(a,2*v,tl,tm);
		build(a,2*v+1,tm+1,tr);
		seg[v]=unite(seg[2*v],seg[2*v+1]);
	}

	node get(int l, int r, int v, int tl, int tr) {
		if (l<=tl && tr<=r) {
			return seg[v];
		}
		if (tr<l || r<tl) {
			return node();
		}
		int tm=tl+(tr-tl)/2;
		return unite(get(l,r,2*v,tl,tm),get(l,r,2*v+1,tm+1,tr));
	}
	node get(int l, int r) {
		return get(l,r,1,0,sze-1);
	}
};

int32_t main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
	int n,q;
	cin >> n >> q;
	vector<pi> ev(n);
	vi nums(2*n);
	for (int i=0; i<n; i++) {
		cin >> ev[i].fi >> ev[i].se;
		nums[2*i]=ev[i].fi;
		nums[2*i+1]=ev[i].se;
	}
	sort(all(nums));
	nums.erase(unique(all(nums)),nums.end());
	vector<pi> vals(nums.size(),{-1,2e9});
	for (int i=0; i<n; i++) {
		ev[i].fi=lower_bound(all(nums),ev[i].fi)-nums.begin();
		ev[i].se=lower_bound(all(nums),ev[i].se)-nums.begin();
		if (vals[ev[i].se].se>ev[i].fi) {
			vals[ev[i].se]={i,ev[i].fi};
		}
	}
	segTree data(nums.size(),vals);
	for (int i=0; i<n; i++) {
		auto a=data.get(ev[i].fi,ev[i].se);
		if (a.val>=ev[i].fi) {
			prv[i][0]=n;
			graph[n].pb(i);
		}
		else {
			prv[i][0]=a.ind;
			graph[a.ind].pb(i);
		}
	}
	int a,b;
	for (int i=0; i<q; i++) {
		cin >> a >> b;
		a--;
		b--;
		if (ev[a].se>ev[b].se) {
			cout << "impossible\n";
			continue;
		}
		else if (a==b) {
			cout << "0\n";
			continue;
		}
		else if (ev[b].fi<=ev[a].se) {
			cout << "1\n";
			continue;
		}
		int ans=0;
		while (b!=n && ev[b].fi>ev[a].se) {
			ans++;
			b=prv[b][0];
		}
		if (b==n) {
			cout << "impossible\n";
		}
		else {
			cout << ans+1 << '\n';
		}
	}
	/*dfs(n);
	int a,b;
	for (int i=0; i<q; i++) {
		cin >> a >> b;
		a--;
		b--;
		if (ev[a].se>ev[b].se) {
			cout << "impossible\n";
			continue;
		}
		else if (a==b) {
			cout << "0\n";
			continue;
		}
		else if (ev[b].fi<=ev[a].se) {
			cout << "1\n";
			continue;
		}
		int ans=0;
		for (int j=logg; j>=0; j--) {
			if (prv[b][j]==n) {
				continue;
			}
			if (ev[prv[b][j]].fi>ev[a].se) {
				b=prv[b][j];
				ans|=(1<<j);
			}
		}
		ans++;
		b=prv[b][0];
		if (b==n || ev[b].fi>ev[a].se) {
			cout << "impossible\n";
		}
		else {
			cout << ans+1 << '\n';
		}
	}*/
}

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