#include <bits/stdc++.h>
using namespace std;
const int MAXN = (1<<18)+5;
const int inf = 1e9+7;
typedef pair<int, int> pii;
int dist[2][2*MAXN];
int sumdist[2*MAXN];
int n, m;
vector<pii> edges[2*MAXN];
void build() {
for (int i = 1; i < m; i++) {
edges[2*i].push_back(pii(i, 0));
edges[2*i+1].push_back(pii(i, 0));
}
}
void assign(int i, int l, int r) {
for (; r > l; l /= 2, r /= 2) {
if (l & 1) edges[l++].push_back(pii(i, 1));
if (r & 1) edges[--r].push_back(pii(i, 1));
}
}
void dijkstra(int curdist[]) {
priority_queue<pii, vector<pii>, greater<pii>> pq;
for (int i = 0; i < 2*m; i++)
pq.push(pii(curdist[i], i));
while (!pq.empty()) {
pii tp = pq.top();
pq.pop();
int cur = tp.second;
if (tp.first > curdist[cur]) continue;
for (pii p: edges[cur]) {
int nxtdist = tp.first+p.second;
if (nxtdist < curdist[p.first]) {
curdist[p.first] = nxtdist;
pq.push(pii(nxtdist, p.first));
}
}
}
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
cin >> n;
m = 1;
for (; m < n; m *= 2);
build();
fill(dist[0], dist[0]+2*m, inf);
fill(dist[1], dist[1]+2*m, inf);
for (int i = 0; i < n; i++) {
int l, r; cin >> l >> r;
l--; r--;
// for (int j = l+n; j <= r+n; j++) edges[j].push_back(pii(i+n, 1));
assign(i+m, l+m, r+m+1);
if (l == 0) dist[0][i+m] = 0;
if (r == n-1) dist[1][i+m] = 0;
}
dijkstra(dist[0]);
dijkstra(dist[1]);
for (int i = 0; i < 2*m; i++) {
sumdist[i] = min(inf, dist[0][i]+dist[1][i]);
}
dijkstra(sumdist);
int q; cin >> q;
for (int i = 0; i < q; i++) {
int s; cin >> s; s += m-1;
cout << ((sumdist[s] < inf) ? sumdist[s]+1 : -1) << '\n';
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
12628 KB |
Output is correct |
2 |
Correct |
6 ms |
12628 KB |
Output is correct |
3 |
Correct |
7 ms |
12628 KB |
Output is correct |
4 |
Correct |
685 ms |
76564 KB |
Output is correct |
5 |
Correct |
451 ms |
53672 KB |
Output is correct |
6 |
Correct |
374 ms |
50272 KB |
Output is correct |
7 |
Correct |
284 ms |
60260 KB |
Output is correct |
8 |
Correct |
243 ms |
62300 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
12628 KB |
Output is correct |
2 |
Correct |
6 ms |
12540 KB |
Output is correct |
3 |
Correct |
6 ms |
12628 KB |
Output is correct |
4 |
Correct |
6 ms |
12628 KB |
Output is correct |
5 |
Correct |
6 ms |
12628 KB |
Output is correct |
6 |
Correct |
6 ms |
12628 KB |
Output is correct |
7 |
Correct |
8 ms |
12628 KB |
Output is correct |
8 |
Correct |
8 ms |
12772 KB |
Output is correct |
9 |
Correct |
6 ms |
12628 KB |
Output is correct |
10 |
Correct |
6 ms |
12628 KB |
Output is correct |
11 |
Correct |
7 ms |
12628 KB |
Output is correct |
12 |
Correct |
7 ms |
12628 KB |
Output is correct |
13 |
Correct |
6 ms |
12756 KB |
Output is correct |
14 |
Correct |
6 ms |
12628 KB |
Output is correct |
15 |
Correct |
6 ms |
12628 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
12628 KB |
Output is correct |
2 |
Correct |
6 ms |
12540 KB |
Output is correct |
3 |
Correct |
6 ms |
12628 KB |
Output is correct |
4 |
Correct |
6 ms |
12628 KB |
Output is correct |
5 |
Correct |
6 ms |
12628 KB |
Output is correct |
6 |
Correct |
6 ms |
12628 KB |
Output is correct |
7 |
Correct |
8 ms |
12628 KB |
Output is correct |
8 |
Correct |
8 ms |
12772 KB |
Output is correct |
9 |
Correct |
6 ms |
12628 KB |
Output is correct |
10 |
Correct |
6 ms |
12628 KB |
Output is correct |
11 |
Correct |
7 ms |
12628 KB |
Output is correct |
12 |
Correct |
7 ms |
12628 KB |
Output is correct |
13 |
Correct |
6 ms |
12756 KB |
Output is correct |
14 |
Correct |
6 ms |
12628 KB |
Output is correct |
15 |
Correct |
6 ms |
12628 KB |
Output is correct |
16 |
Incorrect |
11 ms |
13384 KB |
Output isn't correct |
17 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
12628 KB |
Output is correct |
2 |
Correct |
6 ms |
12540 KB |
Output is correct |
3 |
Correct |
6 ms |
12628 KB |
Output is correct |
4 |
Correct |
6 ms |
12628 KB |
Output is correct |
5 |
Correct |
6 ms |
12628 KB |
Output is correct |
6 |
Correct |
6 ms |
12628 KB |
Output is correct |
7 |
Correct |
8 ms |
12628 KB |
Output is correct |
8 |
Correct |
8 ms |
12772 KB |
Output is correct |
9 |
Correct |
6 ms |
12628 KB |
Output is correct |
10 |
Correct |
6 ms |
12628 KB |
Output is correct |
11 |
Correct |
7 ms |
12628 KB |
Output is correct |
12 |
Correct |
7 ms |
12628 KB |
Output is correct |
13 |
Correct |
6 ms |
12756 KB |
Output is correct |
14 |
Correct |
6 ms |
12628 KB |
Output is correct |
15 |
Correct |
6 ms |
12628 KB |
Output is correct |
16 |
Incorrect |
11 ms |
13384 KB |
Output isn't correct |
17 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
12628 KB |
Output is correct |
2 |
Correct |
6 ms |
12628 KB |
Output is correct |
3 |
Correct |
7 ms |
12628 KB |
Output is correct |
4 |
Correct |
685 ms |
76564 KB |
Output is correct |
5 |
Correct |
451 ms |
53672 KB |
Output is correct |
6 |
Correct |
374 ms |
50272 KB |
Output is correct |
7 |
Correct |
284 ms |
60260 KB |
Output is correct |
8 |
Correct |
243 ms |
62300 KB |
Output is correct |
9 |
Correct |
6 ms |
12628 KB |
Output is correct |
10 |
Correct |
6 ms |
12540 KB |
Output is correct |
11 |
Correct |
6 ms |
12628 KB |
Output is correct |
12 |
Correct |
6 ms |
12628 KB |
Output is correct |
13 |
Correct |
6 ms |
12628 KB |
Output is correct |
14 |
Correct |
6 ms |
12628 KB |
Output is correct |
15 |
Correct |
8 ms |
12628 KB |
Output is correct |
16 |
Correct |
8 ms |
12772 KB |
Output is correct |
17 |
Correct |
6 ms |
12628 KB |
Output is correct |
18 |
Correct |
6 ms |
12628 KB |
Output is correct |
19 |
Correct |
7 ms |
12628 KB |
Output is correct |
20 |
Correct |
7 ms |
12628 KB |
Output is correct |
21 |
Correct |
6 ms |
12756 KB |
Output is correct |
22 |
Correct |
6 ms |
12628 KB |
Output is correct |
23 |
Correct |
6 ms |
12628 KB |
Output is correct |
24 |
Incorrect |
11 ms |
13384 KB |
Output isn't correct |
25 |
Halted |
0 ms |
0 KB |
- |