# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1261840 | CrabCNH | Fire (BOI24_fire) | C++20 | 133 ms | 37920 KiB |
#include <bits/stdc++.h>
#define task "BriantheCrab"
#define int long long
#define pii pair <int, int>
#define fi first
#define se second
#define szf sizeof
#define sz(s) (int)((s).size())
#define all(v) (v).begin(), (v).end()
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
using namespace std;
template <class T> void minimize (T &t, T f) {if (t > f) t = f;}
template <class T> void maximize (T &t, T f) {if (t < f) t = f;}
const int maxN = 2e5 + 5;
const int inf = 1e18 + 7;
const int mod = 1e9 + 7;
const int LOG = 20;
// khong tu code thi khong kha len duoc dau
// biet sol roi thi tu lam not di
int n, m;
pii a[maxN];
int nxt[maxN][LOG];
void solve () {
cin >> n >> m;
vector <int> zip;
for (int i = 1; i <= n; i ++) {
int l, r;
cin >> l >> r;
a[i] = {l, r};
zip.push_back (l);
zip.push_back (r);
}
sort (all (zip));
zip.erase (unique (all (zip)), zip.end ());
for (int i = 1; i <= n; i ++) {
a[i].fi = lower_bound (all (zip), a[i].fi) - zip.begin () + 1;
a[i].se = lower_bound (all (zip), a[i].se) - zip.begin () + 1;
}
m = sz (zip) + 1;
for (int i = 1; i <= n; i ++) {
if (a[i].fi < a[i].se) {
maximize (nxt[a[i].fi][0], a[i].se);
}
}
for (int i = 1; i <= m; i ++) {
maximize (nxt[i][0], nxt[i - 1][0]);
}
for (int j = 1; j < LOG; j ++) {
for (int i = 1; i <= m; i ++) {
maximize (nxt[i][j], nxt[nxt[i][j - 1]][j - 1]);
}
for (int i = 1; i <= m; i ++) {
maximize (nxt[i][j], nxt[i - 1][j]);
}
}
//cout << nxt[4][0] << '\n';
int res = inf;
for (int i = 1; i <= n; i ++) {
if (a[i].fi < a[i].se) {
continue;
}
int cost = 1;
int st = a[i].se, en = a[i].fi;
for (int j = LOG - 1; j >= 0; j --) {
if (nxt[st][j] > 0 && nxt[st][j] < en) {
cost += (1 << j);
//cout << nxt[st][j] << ' ' << st << ' ' << j << '\n';
st = nxt[st][j];
}
}
if (nxt[st][0] >= en) {
minimize (res, cost + 1);
}
}
cout << (res > n ? -1 : res);
return;
}
signed main () {
cin.tie (nullptr) -> sync_with_stdio (false);
if (fopen (task".inp", "r")) {
freopen (task".inp", "r", stdin);
freopen (task".out", "w", stdout);
}
int t = 1;
//cin >> t;
while (t --) {
solve ();
}
return 0;
}
// thfvz
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |