| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 986558 |
2024-05-20T18:16:11 Z |
876pol |
Passport (JOI23_passport) |
C++17 |
|
566 ms |
1048576 KB |
#ifndef LOCAL
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define dbg(...)
#define STRUCT_DBG(...)
#else
#include "lib/debug.h"
#endif
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
using ld = long double;
using pll = pair<ll, ll>;
template <class T>
using vec = vector<T>;
using vll = vector<ll>;
using vpll = vector<pair<ll, ll>>;
using vvll = vector<vector<ll>>;
using vvpll = vector<vector<pair<ll, ll>>>;
template <class T>
using indexed_set =
tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define FOR(i, s, e) for (ll i = (ll)s; i < (ll)e; i++)
#define CFOR(i, s, e) for (ll i = (ll)s; i <= (ll)e; i++)
#define RFOR(i, e, s) for (ll i = (ll)e - 1; i >= (ll)s; i--)
#define TRAV(a, c) for (const auto &a : c)
#define all(x) x.begin(), x.end()
#define MOD 1000000007
// #define MOD 998244353
#define FASTIO
#define PRECISION
// #define FILE "file"
#define SINGLE
// #define MULTIPLE
// #define GOOGLE
void solve() {
ll n;
cin >> n;
vpll a(n + 1);
CFOR(i, 1, n) cin >> a[i].first >> a[i].second;
vvll dp(n + 1, vll(n + 1, INT_MAX)), mx(n + 1, vll(n + 1, -1));
CFOR(i, 1, n) {
CFOR(j, i, n) {
mx[i][j] = max(mx[i][j - 1], a[j].second);
}
}
dp[1][n] = 0;
RFOR(i, n, 1) {
if (mx[1][i] == -1) continue;
dp[1][i] = min(dp[1][i], dp[1][mx[1][i]] + 1);
}
CFOR(i, 2, n) {
CFOR(j, i, n) {
dp[i][j] =
min(dp[i][j], dp[min(i, a[j].first)][max(j, a[j].second)] + 1);
if (i < j) dp[i][j] = min(dp[i][j - 1], dp[i][j]);
}
RFOR(j, n, 1) {
if (mx[i][j] == -1) continue;
dp[i][j] = min(dp[i][j], dp[i][mx[i][j]] + 1);
}
}
ll q;
cin >> q;
FOR(i, 0, q) {
ll x;
cin >> x;
cout << (dp[x][x] == INT_MAX ? -1 : dp[x][x]) << "\n";
}
// sort(all(a), [&](const pass &o1, const pass &o2) { return o1.l <
// o2.l; }); vpll seg(2 * n, {INT_MAX, INT_MAX});
// #define lc(v) (v + 1)
// #define rc(v) (v + 2 * (tm - tl + 1))
// function<void(ll, ll, ll, ll, pll)> update = [&](ll v, ll tl, ll tr,
// ll ind,
// pll x) {
// if (tl == tr && tl == ind) {
// seg[v] = x;
// } else {
// ll tm = (tl + tr) / 2;
// if (ind <= tm) {
// update(lc(v), tl, tm, ind, x);
// } else {
// update(rc(v), tm + 1, tr, ind, x);
// }
// seg[v] = min(seg[lc(v)], seg[rc(v)]);
// }
// };
// function<pll(ll, ll, ll, ll, ll)> query = [&](ll v, ll tl, ll tr, ll
// l,
// ll r) -> pll {
// if (r < tl || tr < l) return {INT_MAX, INT_MAX};
// if (l <= tl && tr <= r) return seg[v];
// ll tm = (tl + tr) / 2;
// return min(query(lc(v), tl, tm, l, r), query(rc(v), tm + 1, tr,
// l, r));
// };
// update(0, 1, n, 1, {0, -1});
// FOR(i, 0, n) {
// TRAV(e, a) {
// if (e.i == 1) continue;
// pll obj = query(0, 1, n, e.l, e.r);
// update(0, 1, n, e.i, {obj.first + 1, min(obj.second, -e.r)});
// }
// }
// vll t1(n + 1), fr1(n + 1);
// CFOR(i, 1, n) t1[i] = query(0, 1, n, i, i).first;
// CFOR(i, 1, n) fr1[i] = query(0, 1, n, i, i).second;
// fill(all(seg), pll{INT_MAX, INT_MAX});
// update(0, 1, n, n, {0, 0});
// FOR(i, 0, n) {
// TRAV(e, a) {
// if (e.i == n) continue;
// pll obj = query(0, 1, n, e.l, e.r);
// update(0, 1, n, e.i, {obj.first + 1, 0});
// }
// }
// vll t2(n + 1);
// CFOR(i, 1, n) t2[i] = query(0, 1, n, i, i).first;
// vll ans(n + 1, INT_MAX);
// CFOR(i, 1, n) {
// CFOR(j, 1, -fr1[i]) {
// ans[i] = min(ans[i], t1[i] + t2[j]);
// }
// }
// ll q;
// cin >> q;
// FOR(i, 0, q) {
// ll x;
// cin >> x;
// cout << (ans[x] == INT_MAX ? -1 : ans[x]) << "\n";
// }
}
int main() {
#ifdef FASTIO
ios_base::sync_with_stdio(false);
cin.tie(NULL);
#endif
#ifdef PRECISION
cout << fixed << setprecision(10);
cerr << fixed << setprecision(10);
#endif
#ifdef FILE
freopen((FILE + string(".in")).c_str(), "r", stdin);
freopen((FILE + string(".out")).c_str(), "w", stdout);
#endif
#ifdef SINGLE
solve();
#endif
#ifdef MULTIPLE
ll t;
cin >> t;
for (ll i = 1; i <= t; i++) {
solve();
}
#endif
#ifdef GOOGLE
ll t;
cin >> t;
for (ll i = 1; i <= t; i++) {
cout << "Case #" << i << ": ";
solve();
}
#endif
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Runtime error |
566 ms |
1048576 KB |
Execution killed with signal 9 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
344 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Incorrect |
0 ms |
420 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
344 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Incorrect |
0 ms |
420 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
344 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Incorrect |
0 ms |
420 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Runtime error |
566 ms |
1048576 KB |
Execution killed with signal 9 |
| 5 |
Halted |
0 ms |
0 KB |
- |
