제출 #1120188

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1120188		vjudge1	Event Hopping (BOI22_events)	C++17	10 / 100	1573 ms	133068 KiB

events

#include <bits/stdc++.h>

#define file(s) freopen(s".in", "r", stdin); freopen(s".out", "w", stdout);
#define adiyer(); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define bitcount(n) __builtin_popcountll(n)
#define all(x) x.begin(), x.end()
#define len(s) (int) s.size()
#define md ((l + r) >> 1)

#define pb push_back
#define S second
#define F first

// #define int long long

using namespace std;

typedef int ll;
typedef long double ld;

const int dx[8] = {1, 0, -1, 0, 1, 1, -1, -1};
const int dy[8] = {0, 1, 0, -1, -1, 1, -1, 1};
const int N = 1e5 + 11;
const int M = 5e3 + 21;
const int MAX = (1 << 16);
const int mod = 998244353;
const long long inf = 1e9 + 10;
const double eps = 1e-9;

ll n, q;
ll l[N], r[N], tl[N], tr[N];

bool was[N];

vector < ll > g[N];

void output(){
	ll d[M][M];
	for(ll i = 0; i <= n + 1; i++)
		for(ll j = 0; j <= n + 1; j++)
			d[i][j] = -1;
	for(ll i = 1; i <= n; i++){
		for(ll j = 1; j <= n; j++){
			if(l[j] <= r[i] && r[i] <= r[j]){
				g[i].pb(j);
			}
		}
	}
	for(ll s = 1; s <= n; s++){
		queue < ll > q;
		fill(was, was + n + 1, 0);
		d[s][s] = 0, was[s] = 1;
		q.push(s);
		while(!q.empty()){
			ll v = q.front();
			q.pop();
			for(ll u : g[v])
				if(!was[u])
					d[s][u] = d[s][v] + 1, q.push(u), was[u] = 1;
		}
	}
	for(ll i = 1; i <= q; i++){
		if(d[tl[i]][tr[i]] == -1) cout << "impossible\n";
		else cout << d[tl[i]][tr[i]] << '\n';
	}
}

void output2(){

}

void output3(){
	vector < pair < pair < ll, ll >, ll > > vec;
	ll ans[n + 3] = {};
	for(ll i = 1; i <= n; i++) vec.pb({{r[i], l[i]}, i});
	sort(all(vec));
	for(ll i = 0; i < n - 1; i++){
		if(vec[i + 1].F.S <= vec[i].F.F && vec[i].F.F <= vec[i + 1].F.F){
			ans[vec[i].S] = vec[i + 1].S;
		}
	}
	for(ll i = 1; i <= q; i++){
		if(tl[i] == tr[i]) cout << "0\n";
		else if(ans[tl[i]] == tr[i]) cout << "1\n";
		else cout << "impossible\n";
	}
}

void read(){
	cin >> n >> q;
	for(ll i = 1; i <= n; i++) cin >> l[i] >> r[i];
	for(ll i = 1; i <= q; i++) cin >> tl[i] >> tr[i];
	if(n <= 5000){
		output();
	}
// 	else if(q <= 100){
// 		output2();
// 	}
	else{
		output3();
	}
}

const bool cases = 0;

signed main(){
//  file("disrupt");
    adiyer();
    int tt = 1;
    if(cases) cin >> tt;
    for(int i = 1; i <= tt; i++){
		read();
    }
}

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