| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 917816 |
2024-01-28T20:09:15 Z |
makrav |
Passport (JOI23_passport) |
C++14 |
|
2000 ms |
50540 KB |
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vei;
typedef vector<vei> vevei;
#define all(a) (a).begin(), (a).end()
#define sz(a) (int) a.size()
#define con cout << "NO\n"
#define coe cout << "YES\n";
#define str string
#define pb push_back
#define ff first
#define sc second
#define ss second
#define pii pair<int, int>
#define mxe max_element
#define mne min_element
#define stf shrink_to_fit
#define f(i, l, r) for (int i = (l); i < (r); i++)
#define double ld
vector<int> Log2;
struct sparsemax {
int n;
vector<pii> a;
vector<vector<int>> sp;
sparsemax() = default;
sparsemax(int n_, vector<pii> a_) {
n = n_;
a = a_;
sp.assign(Log2[n] + 1, vector<int>(n, 0));
build();
}
void build() {
f(i, 0, n) sp[0][i] = i;
f(i, 1, Log2[n] + 1) {
for (int j = 0; j + (1 << i) - 1 < n; j++) {
int li = sp[i - 1][j], ri = sp[i - 1][j + (1 << (i - 1))];
if (a[li].sc > a[ri].sc) sp[i][j] = li;
else if (a[li].sc < a[ri].sc) sp[i][j] = ri;
else sp[i][j] = (a[li].ff < a[ri].ff ? li : ri);
}
}
}
int get(int l, int r) {
int lg = Log2[r - l + 1];
int li = sp[lg][l], ri = sp[lg][r - (1 << lg) + 1];
if (a[li].sc > a[ri].sc) return li;
else if (a[li].sc < a[ri].sc) return ri;
else return (a[li].ff < a[ri].ff ? li : ri);
}
};
struct sparsemin {
int n;
vector<pii> a;
vector<vector<int>> sp;
sparsemin() = default;
sparsemin(int n_, vector<pii> a_) {
n = n_;
a = a_;
sp.assign(Log2[n] + 1, vector<int>(n, 0));
build();
}
void build() {
f(i, 0, n) sp[0][i] = i;
f(i, 1, Log2[n] + 1) {
for (int j = 0; j + (1 << i) - 1 < n; j++) {
int li = sp[i - 1][j], ri = sp[i - 1][j + (1 << (i - 1))];
if (a[li].ff > a[ri].ff) sp[i][j] = ri;
else if (a[li].ff < a[ri].ff) sp[i][j] = li;
else sp[i][j] = (a[li].sc < a[ri].sc ? ri : li);
}
}
}
int get(int l, int r) {
int lg = Log2[r - l + 1];
int li = sp[lg][l], ri = sp[lg][r - (1 << lg) + 1];
if (a[li].ff > a[ri].ff) return ri;
else if (a[li].ff < a[ri].ff) return li;
else return (a[li].sc < a[ri].sc ? ri : li);
}
};
struct node {
int mx;
node() = default;
node(int a) {
mx = a;
}
};
struct segtree {
int n;
vector<int> a;
vector<node> t;
segtree() = default;
segtree(int n_, vector<int> a_) {
n = n_;
a = a_;
t.resize(4 * n);
build(1, 0, n);
}
void build(int v, int tl, int tr) {
if (tl + 1 == tr) {
t[v] = node(a[tl]);
return;
}
int tm = (tl + tr) / 2;
build(v * 2, tl, tm);
build(v * 2 + 1, tm, tr);
t[v].mx = min(t[v * 2].mx, t[v * 2 + 1].mx);
}
int req(int v, int tl, int tr, int l, int r) {
if (l <= tl && tr <= r) return t[v].mx;
if (tr <= l || tl >= r) return 1e9;
int tm = (tl + tr) / 2;
return min(req(v * 2, tl, tm, l, r), req(v * 2 + 1, tm, tr, l, r));
}
void upd(int v, int tl, int tr, int pos, int val) {
if (tl + 1 == tr) {
t[v] = node(val);return;
}
int tm = (tl + tr) / 2;
if (pos < tm) {
upd(v * 2, tl, tm, pos, val);
}
else {
upd(v * 2 + 1, tm, tr, pos, val);
}
t[v].mx = min(t[v * 2].mx, t[v * 2 + 1].mx);
}
};
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
Log2.assign(200010, 0);
for (int i = 2; i < 200010; i++) {
Log2[i] = Log2[i / 2] + 1;
}
int n; cin >> n;
vector<pair<int, int>> a(n), ls(n), rs(n);
vector<int> R(n), L(n), tor(n, 1e9), tol(n, 1e9);
f(i, 0, n) {
cin >> a[i].ff >> a[i].sc;
a[i].ff--; a[i].sc--;
R[i] = a[i].sc;
L[i] = a[i].ff;
ls[i] = { L[i], i };
rs[i] = { R[i], i };
}
sparsemax sp(n, a);
sparsemin sp2(n, a);
sort(all(rs));
for (int i = n - 1; i >= 0; i--) {
if (a[rs[i].sc].sc == n - 1) {
tor[rs[i].sc] = 0;
continue;
}
int maxr = sp.get(a[rs[i].sc].ff, a[rs[i].sc].sc);
//cout << rs[i].sc << ' ';
//cout << maxr << '\n';
tor[rs[i].sc] = tor[maxr] + 1;
}
sort(all(ls));
for (int i = 0; i < n; i++) {
if (a[ls[i].sc].ff == 0) {
tol[ls[i].sc] = 0;
continue;
}
int minl = sp2.get(a[ls[i].sc].ff, a[ls[i].sc].sc);
tol[ls[i].sc] = tol[minl] + 1;
}
vector<int> totans(n, 0), ANS(n, 1e9);
vector<pair<int, int>> fa;
f(i, 0, n) {
totans[i] = tol[i] + tor[i];
fa.pb({ totans[i], i });
}
sort(all(fa));
f (j, 0, n) {
segtree sg(n, vector<int>(n, 1e9));
f(i, 0, n) {
//cout << fa[i].ff << ' ' << fa[i].sc << ' ';
ANS[fa[i].sc] = min(ANS[fa[i].sc], min(fa[i].ff, sg.req(1, 0, n, a[fa[i].sc].ff, a[fa[i].sc].sc + 1) + 1));
//cout << ANS[fa[i].sc] << '\n';
sg.upd(1, 0, n, fa[i].sc, ANS[fa[i].sc]);
}
}
int q; cin >> q;
while (q--) {
int x; cin >> x;
x--;
cout << (ANS[x] >= 1e9 ? -1 : ANS[x] + 1) << '\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 3 |
Correct |
1 ms |
1112 KB |
Output is correct |
| 4 |
Execution timed out |
2047 ms |
50540 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 3 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 6 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 7 |
Correct |
1 ms |
1112 KB |
Output is correct |
| 8 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 9 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 10 |
Correct |
1 ms |
1112 KB |
Output is correct |
| 11 |
Correct |
7 ms |
1116 KB |
Output is correct |
| 12 |
Correct |
7 ms |
1112 KB |
Output is correct |
| 13 |
Correct |
10 ms |
1116 KB |
Output is correct |
| 14 |
Correct |
7 ms |
1112 KB |
Output is correct |
| 15 |
Incorrect |
7 ms |
1112 KB |
Output isn't correct |
| 16 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 3 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 6 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 7 |
Correct |
1 ms |
1112 KB |
Output is correct |
| 8 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 9 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 10 |
Correct |
1 ms |
1112 KB |
Output is correct |
| 11 |
Correct |
7 ms |
1116 KB |
Output is correct |
| 12 |
Correct |
7 ms |
1112 KB |
Output is correct |
| 13 |
Correct |
10 ms |
1116 KB |
Output is correct |
| 14 |
Correct |
7 ms |
1112 KB |
Output is correct |
| 15 |
Incorrect |
7 ms |
1112 KB |
Output isn't correct |
| 16 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 3 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 6 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 7 |
Correct |
1 ms |
1112 KB |
Output is correct |
| 8 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 9 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 10 |
Correct |
1 ms |
1112 KB |
Output is correct |
| 11 |
Correct |
7 ms |
1116 KB |
Output is correct |
| 12 |
Correct |
7 ms |
1112 KB |
Output is correct |
| 13 |
Correct |
10 ms |
1116 KB |
Output is correct |
| 14 |
Correct |
7 ms |
1112 KB |
Output is correct |
| 15 |
Incorrect |
7 ms |
1112 KB |
Output isn't correct |
| 16 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 3 |
Correct |
1 ms |
1112 KB |
Output is correct |
| 4 |
Execution timed out |
2047 ms |
50540 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
