#include<fstream>
using namespace std;
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
const ld PI = 3.14159265359;
const int x[4] = {1, -1, 0, 0};
const int y[4] = {0, 0, 1, -1};
const ll mod = 1e9 + 7;
const int mxn = 5e5, mxm = 1e5, sq = 400;
const int base = (1 << 18);
const ll inf = 1e9;
const ld pre = 1e-6;
//cool problem!
int n;
int l[mxn + 1], r[mxn + 1], id, lson[2 * mxn + 5], rson[2 * mxn + 5];
vt<pii>adj[2 * mxn + 5];
vt<ll>d1, d2, d3;
int build(int nd, int l, int r){
if(l == r)return(l);
int mid = (l + r) >> 1;
int ls = build(nd << 1, l, mid), rs = build(nd << 1 | 1, mid + 1, r);
++id;
lson[id] = ls; rson[id] = rs;
adj[lson[id]].emplace_back(id, 0); adj[rson[id]].emplace_back(id, 0);
return(id);
}
void upd(int nd, int l, int r, int ql, int qr, int u){
if(ql > r || qr < l)return;
if(ql <= l && qr >= r){
adj[nd].emplace_back(u, 1);
return;
}
int mid = (l + r) >> 1;
upd(lson[nd], l, mid, ql, qr, u); upd(rson[nd], mid + 1, r, ql, qr, u);
}
void find(vt<int>&d){
deque<int>dq;
for(int i = 1; i <= n; i++){
if(d[i] != inf)dq.pb(i);
}
while(!dq.empty()){
int u = dq.front(); dq.pop_front();
for(auto [v, w]: adj[u]){
if(d[v] > d[u] + w){
d[v] = d[u] + w;
if(w){
dq.pb(v);
}else{
dq.push_front(v);
}
}
}
}
}
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n;
id = n;
int root = build(1, 1, n);
forr(i, 1, n + 1){
cin >> l[i] >> r[i];
upd(root, 1, n, l[i], r[i], i);
}
d1.resize(2 * n + 5, inf); d1[1] = 0;
find(d1);
d1[1] = 1;
d2.resize(2 * n + 5, inf); d2[n] = 0;
find(d2);
d2[n] = 1;
d3.resize(4 * n + 1, inf);
for(int i = 1; i <= n; i++){
d3[i] = d1[i] + d2[i];
}
find(d3);
int q; cin >> q;
forr(i, 0, q){
int x; cin >> x;
if(d3[x] >= 1e9)cout << -1 << "\n";
else cout << d3[x] - 1 << "\n";
}
return(0);
}
Compilation message
passport.cpp:10:12: error: 'vector' does not name a type
10 | #define vt vector
| ^~~~~~
passport.cpp:27:1: note: in expansion of macro 'vt'
27 | vt<pii>adj[2 * mxn + 5];
| ^~
passport.cpp:10:12: error: 'vector' does not name a type
10 | #define vt vector
| ^~~~~~
passport.cpp:28:1: note: in expansion of macro 'vt'
28 | vt<ll>d1, d2, d3;
| ^~
passport.cpp: In function 'int build(int, int, int)':
passport.cpp:36:5: error: 'adj' was not declared in this scope
36 | adj[lson[id]].emplace_back(id, 0); adj[rson[id]].emplace_back(id, 0);
| ^~~
passport.cpp: In function 'void upd(int, int, int, int, int, int)':
passport.cpp:43:9: error: 'adj' was not declared in this scope
43 | adj[nd].emplace_back(u, 1);
| ^~~
passport.cpp: At global scope:
passport.cpp:49:6: error: variable or field 'find' declared void
49 | void find(vt<int>&d){
| ^~~~
passport.cpp:10:12: error: 'vector' was not declared in this scope
10 | #define vt vector
| ^~~~~~
passport.cpp:49:11: note: in expansion of macro 'vt'
49 | void find(vt<int>&d){
| ^~
passport.cpp:2:1: note: 'std::vector' is defined in header '<vector>'; did you forget to '#include <vector>'?
1 | #include<fstream>
+++ |+#include <vector>
2 | using namespace std;
passport.cpp:49:14: error: expected primary-expression before 'int'
49 | void find(vt<int>&d){
| ^~~
passport.cpp: In function 'int main()':
passport.cpp:70:35: error: 'cin' was not declared in this scope
70 | ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
| ^~~
passport.cpp:2:1: note: 'std::cin' is defined in header '<iostream>'; did you forget to '#include <iostream>'?
1 | #include<fstream>
+++ |+#include <iostream>
2 | using namespace std;
passport.cpp:70:47: error: 'cout' was not declared in this scope
70 | ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
| ^~~~
passport.cpp:70:47: note: 'std::cout' is defined in header '<iostream>'; did you forget to '#include <iostream>'?
passport.cpp:79:5: error: 'd1' was not declared in this scope
79 | d1.resize(2 * n + 5, inf); d1[1] = 0;
| ^~
passport.cpp:82:5: error: 'd2' was not declared in this scope
82 | d2.resize(2 * n + 5, inf); d2[n] = 0;
| ^~
passport.cpp:87:5: error: 'd3' was not declared in this scope
87 | d3.resize(4 * n + 1, inf);
| ^~
