Submission #849505

#	Time	Username	Problem	Language	Result	Execution time	Memory
849505		vjudge1	Event Hopping (BOI22_events)	C++17	10 / 100	1547 ms	15952 KiB

events

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define F first
#define S second
#define endl '\n'
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
const int mod = 1e9 + 7;
const int N = 1e5 + 15;
const ll inf = 1e18;
int n,q;
int dis[N];
struct segtree{
	static const int off = (1<<18);
	int t[off*2];
	int unit;
	void init(){
		memset(t, 0x3f, sizeof(t));
		unit = t[0];
	}
	void update(int i,int u){
		i+=off;
		if (u >= t[i]) return;
		t[i] = u;
		while (i/=2){
			t[i] = min(t[i*2],t[i*2+1]);
		}
	}
	int get(int l, int r, int idx=1, int lo=0, int hi=off){
		if (lo>=r||hi<=l) return unit;
		if (lo>=l&&hi<=r) return t[idx];
		int mi = (lo+hi)/2;
		return min(get(l,r,idx*2,lo,mi),get(l,r,idx*2+1,mi,hi));
	}
} seg;
vector<array<int, 3>> a;
bool cmp(array<int, 3> A, array<int, 3> B){
	if (A[1]!=B[1]) return A[1] < B[1];
	return A[0] < B[0];
}
pii b[N];
int solve(int root, int to){
	dis[root] = 0;
	seg.update(b[root].S, 0);
	for (int i=0;i<n;i++){
		if (a[i][2]==root) continue;
		int u = 1+seg.get(a[i][0], a[i][1]+1);
		dis[a[i][2]] = u;
		seg.update(a[i][1], u);
	}
	return dis[to];
}

int32_t main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin >> n >> q;
	a.resize(n);
	map<int,int> mp;
	for (int i=0;i<n;i++){
		int s, e; cin >> s >> e;
		mp[s]; mp[e];
		b[i] = {s, e};
	}
	int cnt = 0;
	for (auto &it : mp) {
		it.S = cnt++;
	}
	for (int i=0;i<n;i++){
		b[i] = {mp[b[i].F], mp[b[i].S]};
		a[i] = {b[i].F, b[i].S, i};
	}
	sort(all(a),cmp);
	while (q--){
		int s, e;
		cin >> s >> e;
		s--;e--;
		memset(dis, 0x3f, sizeof(dis));
		seg.init();
		int ans = solve(s, e);
		if (ans>n) cout << "impossible\n";
		else cout << ans << endl;
	}
}

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