#include <cstdio>
#include <random>
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <cassert>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>
#include <functional>
#include <chrono>
#define ll long long
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
using namespace std;
// вправо, вниз, влево, вверх
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
// ход конем
//int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2};
//int dy[] = {1, 2, 2, 1, -1, -2, -2, -1};
mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
mt19937_64 rnd64(chrono::system_clock::now().time_since_epoch().count());
int rndInteger (int l, int r) {
return uniform_int_distribution<int> (l, r)(rnd);
}
const int MOD = (int) 998244353;
const int N = (int) 3e5 + 7;
int n, q;
int l[N], r[N];
int d[4][N];
int vis[N * 4];
void init() {
memset(vis, 0, sizeof vis);
}
vector<int> g;
void get(int l, int r, int v = 1, int tl = 1, int tr = n) {
if(tr < l || r < tl || vis[v]) return;
if(tl == tr) {
g.push_back(tl);
vis[v] = true;
return;
}
int tm = (tl+tr) >> 1;
get(l, r, v<<1, tl, tm);
get(l, r, v<<1|1, tm+1, tr);
vis[v] = (vis[v<<1] & vis[v<<1|1]);
}
void djk(int id, int st) {
for (int v = 1; v <= n; ++v) {
d[id][v] = 1e9;
}
d[id][st] = 0;
set<pair<int,int>> s;
s.insert({1, st});
//cout << "start: " << st << endl;
while(sz(s)) {
int v = s.begin()->second;
s.erase(s.begin());
get(l[v], r[v]);
// cout << "djk: " << v << endl;
for (int to : g) {
// cout << "adj: " << to << ' ';
if(d[id][to] > d[id][v] + 1) {
s.erase({d[id][to], to});
d[id][to] = d[id][v] + 1;
s.insert({d[id][to], to});
}
}
// cout << '\n';
g.clear();
}
}
int main() {
#ifdef LOCAL
freopen("in.txt", "r", stdin);
#endif
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> l[i] >> r[i];
}
init();
djk(0, 1);
init();
djk(1, n);
init();
set<pair<int,int>> s;
for (int v = 1; v <= n; ++v) {
// cout << "here: " << v << ' ' << d[0][v] << ' ' << d[1][v] << '\n';
if(v == 1) {
d[2][v] = d[0][n];
} else if(v == n) {
d[2][v] = d[1][v];
} else {
d[2][v] = d[1][v] + d[0][v] - 1;
}
if(d[2][v] < 1e9) {
s.insert({d[2][v], v});
}
}
while(sz(s)) {
while(sz(s)) {
int v = s.begin()->second;
s.erase(s.begin());
get(l[v], r[v]);
for (int to : g) {
if(d[2][to] > d[2][v] + 1) {
s.erase({d[2][to], to});
d[2][to] = d[2][v] + 1;
s.insert({d[2][to], to});
}
}
g.clear();
}
}
cin >> q;
for(; q; --q) {
int x;
cin >> x;
cout << d[2][x] << '\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
4948 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
4940 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
4940 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
4940 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
4948 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
