제출 #1303480

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1303480		g4yuhg	Fire (BOI24_fire)	C++20	100 / 100	301 ms	72988 KiB

Main

#include<bits/stdc++.h>
typedef long long ll;
#define pii pair<ll, ll>
#define fi first
#define se second
#define endl '\n'
#define TASK ""
#define N 500006
#define LOG 19
using namespace std;

const ll inf = 1e18;

bool ghuy4g;

ll n, m, cur, sz;
vector<ll> ns;

pii p[N];
vector<pii> st;

ll par[N][LOG + 2];

void pre() {
	sort(p + 1, p + 1 + cur);
	/*cout << "sz " << sz << endl;
	for (int i = 1; i <= cur; i ++) {
		cout << p[i].fi << " " << p[i].se << endl;
	}*/
	ll mx = 0;
	ll id = 1;
	for (auto it : st) {
		//if (it.fi == 1) continue;
		mx = max(mx, it.se);
	}
	//cout << mx << endl;
	for (int i = 1; i <= sz; i ++) {
		while (id <= cur && p[id].fi <= i) {
			mx = max(mx, p[id].se);
			id ++ ;
		}
		par[i][0] = mx;
		//cout << " i " << i << " " << par[i][0] << endl;
	}
	par[sz + 1][0] = sz + 1;
	par[sz][0] = sz;
	for (int j = 1; j <= LOG; j ++) {
		for (int i = 1; i <= sz; i ++) {
			ll p = par[i][j - 1];
			par[i][j] = par[p][j - 1];
		}
	}
}

void solve() {
	ll ans = inf;
	for (auto it : st) {
		if (it.fi == 1) {
			ll cur = it.se;
			ll res = 0;
			for (int j = LOG; j >= 0; j --) {
				if (par[cur][j] < sz) {
					cur = par[cur][j];
					res += (1 << j);
				}
			}
			cur = par[cur][0];
			res ++ ;
			if (cur >= sz) {
				ans = min(ans, res + 1);
			}
		}
		else {
			ll cur = it.se;
			ll res = 0;
			for (int j = LOG; j >= 0; j --) {
				if (par[cur][j] < it.fi) {
					cur = par[cur][j];
					res += (1 << j);
				}
			}
			cur = par[cur][0];
			res ++ ;
			if (cur >= it.fi) {
				ans = min(ans, res + 1);
			}
		}
	}
	if (ans == inf) {
		ans = -1;
	}
	cout << ans << endl;
}

bool klinh;

signed main() {
   	//freopen("sort.inp", "r", stdin);
	//freopen("sort.out", "w", stdout);
	//srand(time(0));
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
   	cin >> n >> m;
   	ns.push_back(m);
   	for (int i = 1; i <= n; i ++) {
   		ll u, v;
   		cin >> u >> v;
   		if (u <= v && u > 0) {
   			p[++ cur] = {u, v};
   		}
   		else if (v == 0) {
   			v = m;
   			p[++ cur] = {u, v};
   		}
   		else {
   			st.push_back({u, v});
   		}
   		//cout << " u v " << u << " " << v << endl;
   		ns.push_back(u);
   		ns.push_back(v);
   	}
   	sort(ns.begin(), ns.end());
   	ns.resize(unique(ns.begin(), ns.end()) - ns.begin());
   	sz = ns.size();
   	/*for (auto it : ns) {
   		cout << it << " ";
   	}
   	cout << endl;*/
   	for (int i = 1; i <= cur; i ++) {
   		p[i].fi = lower_bound(ns.begin(), ns.end(), p[i].fi) - ns.begin() + 1;
   		p[i].se = lower_bound(ns.begin(), ns.end(), p[i].se) - ns.begin() + 1;
   	}
   	for (auto &it : st) {
   		it.fi = lower_bound(ns.begin(), ns.end(), it.fi) - ns.begin() + 1;
   		it.se = lower_bound(ns.begin(), ns.end(), it.se) - ns.begin() + 1;
   		//cout << " it " << it.fi << " " << it.se << endl;
   	}
   	
   	pre();
   	solve();
    
   	cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
   	cerr << fabs(&klinh - &ghuy4g) / 1048576.0;
   	
}

• Subtask 1: 14 / 14
• Subtask 2: 17 / 17
• Subtask 3: 9 / 9
• Subtask 4: 13 / 13
• Subtask 5: 21 / 21
• Subtask 6: 26 / 26