| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 784140 |
2023-07-15T18:37:14 Z |
RushB |
Passport (JOI23_passport) |
C++17 |
|
3 ms |
4948 KB |
#include <bits/stdc++.h>
using namespace std;
using ar = array<int, 2>;
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
const int64_t INF = 1 << 30;
const int N = 2e5 + 5;
const int L = 19;
ar mxR[N][L], mnL[N][L];
array<int, 3> a[N];
vector<int> adj[N];
int lft[N], rht[N], dist[N], n;
bitset<N> isL, isR;
int maxR(int l, int r) {
int t = __lg(r - l + 1);
return max(mxR[l][t], mxR[r - (1 << t) + 1][t])[1];
}
int minL(int l, int r) {
int t = __lg(r - l + 1);
return min(mnL[l][t], mnL[r - (1 << t) + 1][t])[1];
}
signed main() {
ios::sync_with_stdio(0), cin.tie(0);
cin >> n;
FOR(i, 0, n) {
cin >> a[i][0] >> a[i][1];
a[i][0]--, a[i][1]--;
a[i][2] = i;
}
for (int i = n - 1; i >= 0; i--) {
mxR[i][0] = {a[i][1], i}, mnL[i][0] = {a[i][0], i};
for (int j = 1; i + (1 << j) <= n; j++) {
mxR[i][j] = max(mxR[i][j - 1], mxR[i + (1 << j - 1)][j - 1]);
mnL[i][j] = min(mnL[i][j - 1], mnL[i + (1 << j - 1)][j - 1]);
}
}
FOR(i, 0, n) {
int x = minL(a[i][0], a[i][1]);
assert(a[i][0] <= x && x <= a[i][1]);
lft[i] = (!a[i][0] ? 0 : lft[x] + 1);
isL[i] = isL[x] | !a[i][0];
adj[x].push_back(i);
}
for (int i = n - 1; i >= 0; i--) {
int x = maxR(a[i][0], a[i][1]);
assert(a[i][0] <= x && x <= a[i][1]);
rht[i] = (a[i][1] == n - 1 ? 0 : rht[x] + 1);
isR[i] = isR[x] | (a[i][1] == n - 1);
adj[x].push_back(i);
}
set<pair<int, int>> S;
FOR(i, 0, n) {
dist[i] = (isL[i] && isR[i] ? lft[i] + rht[i] + 1 : INF);
S.insert({dist[i], i});
}
while (S.size()) {
int v = S.begin()->second;
S.erase(S.begin());
for (auto u: adj[v]) if (dist[v] + 1 < dist[u]) {
S.erase({dist[u], u});
dist[u] = dist[v] + 1;
S.insert({dist[u], u});
}
}
FOR(i, 0, n)
cout << (dist[i] >= INF ? -1 : dist[i]) << '\n';
return 0;
}
Compilation message
passport.cpp: In function 'int main()':
passport.cpp:34:72: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
34 | mxR[i][j] = max(mxR[i][j - 1], mxR[i + (1 << j - 1)][j - 1]);
| ~~^~~
passport.cpp:35:72: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
35 | mnL[i][j] = min(mnL[i][j - 1], mnL[i + (1 << j - 1)][j - 1]);
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
