/**
_ _ __ _ _ _ _ _ _
|a ||t ||o d | |o |
| __ _| | _ | __| _ |
| __ |/_ | __ /__\ / _\|
**/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N_MAX = 200000;
const int INF = INT_MAX / 2;
int N;
int L[N_MAX + 2], R[N_MAX + 2];
int Q;
vector <pair <int, int>> adj[N_MAX * 4 + 2];
int encode[N_MAX * 4 + 2];
void build (int node, int l, int r) {
if (l == r) {
encode[node] = l;
return;
}
encode[node] = node + N;
int mid = (l + r) / 2;
int left = node * 2, right = node * 2 + 1;
build(left, l, mid);
build(right, mid + 1, r);
adj[encode[left]].push_back({encode[node], 0});
adj[encode[right]].push_back({encode[node], 0});
}
void build () {
build(1, 1, N);
}
void connect_range (int node, int l, int r, int i) {
if (L[i] <= l && r <= R[i]) {
adj[encode[node]].push_back({i, 1});
return;
}
int mid = (l + r) / 2;
int left = node * 2, right = node * 2 + 1;
if (L[i] <= mid) {
connect_range(left, l, mid, i);
}
if (mid + 1 <= R[i]) {
connect_range(right, mid + 1, r, i);
}
}
void connect_range (int i) {
connect_range(1, 1, N, i);
}
int dp_left[N_MAX * 4 + 2];
int dp_right[N_MAX * 4 + 2];
int dp_full[N_MAX * 4 + 2];
vector <int> at_dist[N_MAX + 2];
bool seen[N_MAX * 4 + 2];
void Dijkstra (int dist[]) {
for (int i = 1; i <= N; i++) {
if (dist[i] < N) {
at_dist[dist[i]].push_back(i);
}
seen[i] = false;
}
fill(dist + N + 1, dist + N * 4 + 1, INF);
for (int d = 0; d < N; d++) {
while (at_dist[d].empty() == false) {
int u = at_dist[d].back();
at_dist[d].pop_back();
if (seen[u] == true) {
continue;
}
seen[u] = true;
for (pair <int, int> e : adj[u]) {
int v, c; tie(v, c) = e;
if (dist[u] + c < dist[v]) {
dist[v] = dist[u] + c;
if (dist[v] < N) {
at_dist[dist[v]].push_back(v);
}
}
}
}
}
}
int main () {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> N;
build();
for (int i = 1; i <= N; i++) {
cin >> L[i] >> R[i];
connect_range(i);
dp_left[i] = (L[i] == 1 ? 0 : INF);
dp_right[i] = (R[i] == N ? 0 : INF);
}
Dijkstra(dp_left);
Dijkstra(dp_right);
for (int i = 1; i <= N; i++) {
dp_full[i] = min(INF, dp_left[i] + dp_right[i]);
}
Dijkstra(dp_full);
cin >> Q;
while (Q--) {
int i;
cin >> i;
cout << (dp_full[i] != INF ? dp_full[i] + 1 : -1) << "\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
33116 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
33116 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
33116 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
33116 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
33116 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
