#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define MP make_pair
#define pb push_back
#define REP(i,n) for(int (i) = 0; (i) < (n); (i)++)
void fastio() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
}
const double EPS = 0.00001;
const int INF = 1e9+500;
const int N = 2e5+5;
const int ALPH = 26;
const int LGN = 25;
const int MOD = 1e9+7;
int n,m,q;
vector<int> que;
vector<int> dp;
vector<int> dpL, dpR;
void dbg(vector<int> x) {
for(auto c : x) {
cout<<c<<" ";
}
cout<<"\n";
}
struct NodeTree {
vector<vector<int> > data;
vector<int> vis;
int sz;
NodeTree(int sz) {
data.assign(4*(sz + 3), vector<int>());
this->sz = sz;
vis.assign(sz + 3, 0);
}
void update(int tl, int tr, int v, int l, int r, int node) {
if(tl >= l && tr <= r) {
data[v].pb(node);
return;
}
if(tl > r || tr < l) {
return;
}
int tm = (tl + tr) >> 1;
update(tl, tm, v*2, l, r, node);
update(tm + 1, tr, v*2+1, l, r, node);
}
void update(int l, int r, int node) {
update(0, sz, 1, l, r, node);
}
void query(int tl, int tr, int v, int ind, vector<int> &vec) {
while(data[v].size()) {
if(!vis[data[v].back()]) {
vis[data[v].back()] = 1;
vec.pb(data[v].back());
}
data[v].pop_back();
}
if(tl == tr) {
return;
}
int tm = (tl + tr) >> 1;
if(ind <= tm) {
query(tl, tm, v*2, ind, vec);
}
else {
query(tm + 1, tr, v*2+1, ind, vec);
}
}
void query(int ind, vector<int> &vec) {
query(0, sz, 1, ind, vec);
}
};
struct Inter {
int l, r, ind;
Inter(int l, int r, int i) {
this->l = l;
this->r = r;
this->ind = i;
}
Inter() {
l = 0; r = 0; ind = 0;
}
void input(int i) {
cin>>l>>r;
ind = i;
}
void print() {
cout<<"INTERVAL\n";
cout<<"l:"<<l<<" r:"<<r<<" ind:"<<ind<<"\n";
}
};
vector<Inter> inter;
void find_sp(vector<int> &src, vector<int> &sp, NodeTree &st) {
queue<int> ord;
sp.assign(n + 3, INF);
// cout<<"src:\n";
// dbg(src);
for(auto c : src) {
ord.push(c);
sp[c] = 0;
}
while(ord.size()) {
auto cur = ord.front();
ord.pop();
vector<int> ch;
st.query(cur , ch);
// cout<<"cur:"<<cur<<" ch:\n";
// dbg(ch);
for(auto c : ch) {
sp[c] = sp[cur] + 1;
ord.push(c);
}
}
}
void bfs(vector<array<int,2> > &entr, vector<int> &sp, NodeTree &st) { // find sp with entry times
queue<int> ord;
sort(entr.rbegin(), entr.rend());
// cout<<"ENTR:\n";
// for(auto c : entr) {
// cout<<c[0]<<" "<<c[1]<<"\n";
// }
sp.assign(n+3, INF);
ord.push(entr.back()[1]);
sp[entr.back()[1]] = entr.back()[0];
st.vis[entr.back()[1]] = 1;
entr.pop_back();
while(ord.size()) {
auto cur = ord.front();
ord.pop();
while(entr.size() && entr.back()[0] <= sp[cur]) {
if(st.vis[entr.back()[1]]) {
entr.pop_back();
continue;
}
ord.push(entr.back()[1]);
sp[entr.back()[1]] = entr.back()[0];
st.vis[entr.back()[1]] = 1;
entr.pop_back();
}
vector<int> ch;
st.query(cur, ch);
for(auto c : ch) {
ord.push(c);
sp[c] = sp[cur] + 1;
}
}
}
void prec() {
NodeTree Ltree(n), Rtree(n);
vector<int> src;
for(int i = 1; i<=n; i++) {
if(inter[i].l == 1) {
src.pb(i);
}
else {
Ltree.update(inter[i].l, inter[i].r, i);
}
}
find_sp(src, dpL, Ltree);
src.clear();
for(int i = 1; i<=n; i++) {
if(inter[i].r == n) {
src.pb(i);
}
else {
Rtree.update(inter[i].l, inter[i].r, i);
}
}
find_sp(src, dpR, Rtree);
vector<array<int,2> > entr(n);
NodeTree nt(n);
for(int i = 1; i<=n; i++) {
entr[i - 1] = {dpL[i] + dpR[i], i};
nt.update(inter[i].l, inter[i].r, i);
}
bfs(entr, dp, nt);
}
inline void solve() {
cin>>n;
inter.assign(n + 1, Inter());
REP(i,n) {
inter[i + 1].input(i + 1);
}
cin>>q;
que.assign(q+3, 0);
REP(i,q) {
cin>>que[i + 1];
}
prec();
// cout<<"dpL:\n";
// dbg(dpL);
// cout<<"dpR:\n";
// dbg(dpR);
// cout<<"dp:\n";
// dbg(dp);
for(int i = 1; i<=q; i++) {
if(dp[que[i]] == INF) dp[que[i]] = -2;
cout<<dp[que[i]] + 1<<"\n";
}
}
signed main() {
fastio();
int test = 1;
//cin>>test;
while(test--) {
solve();
}
}
Compilation message
passport.cpp: In function 'void solve()':
passport.cpp:9:26: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
9 | #define REP(i,n) for(int (i) = 0; (i) < (n); (i)++)
| ^
passport.cpp:210:5: note: in expansion of macro 'REP'
210 | REP(i,n) {
| ^~~
passport.cpp:9:26: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
9 | #define REP(i,n) for(int (i) = 0; (i) < (n); (i)++)
| ^
passport.cpp:215:5: note: in expansion of macro 'REP'
215 | REP(i,q) {
| ^~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
721 ms |
127476 KB |
Output is correct |
5 |
Correct |
307 ms |
98448 KB |
Output is correct |
6 |
Correct |
241 ms |
99668 KB |
Output is correct |
7 |
Correct |
118 ms |
82840 KB |
Output is correct |
8 |
Correct |
86 ms |
68504 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
708 KB |
Output is correct |
9 |
Correct |
0 ms |
500 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
460 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
604 KB |
Output is correct |
14 |
Correct |
1 ms |
348 KB |
Output is correct |
15 |
Correct |
1 ms |
344 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
708 KB |
Output is correct |
9 |
Correct |
0 ms |
500 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
460 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
604 KB |
Output is correct |
14 |
Correct |
1 ms |
348 KB |
Output is correct |
15 |
Correct |
1 ms |
344 KB |
Output is correct |
16 |
Correct |
4 ms |
1628 KB |
Output is correct |
17 |
Correct |
4 ms |
1628 KB |
Output is correct |
18 |
Correct |
4 ms |
2136 KB |
Output is correct |
19 |
Correct |
4 ms |
1884 KB |
Output is correct |
20 |
Correct |
3 ms |
1880 KB |
Output is correct |
21 |
Correct |
3 ms |
1628 KB |
Output is correct |
22 |
Correct |
2 ms |
1372 KB |
Output is correct |
23 |
Correct |
3 ms |
1796 KB |
Output is correct |
24 |
Correct |
3 ms |
1624 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
708 KB |
Output is correct |
9 |
Correct |
0 ms |
500 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
460 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
604 KB |
Output is correct |
14 |
Correct |
1 ms |
348 KB |
Output is correct |
15 |
Correct |
1 ms |
344 KB |
Output is correct |
16 |
Correct |
4 ms |
1628 KB |
Output is correct |
17 |
Correct |
4 ms |
1628 KB |
Output is correct |
18 |
Correct |
4 ms |
2136 KB |
Output is correct |
19 |
Correct |
4 ms |
1884 KB |
Output is correct |
20 |
Correct |
3 ms |
1880 KB |
Output is correct |
21 |
Correct |
3 ms |
1628 KB |
Output is correct |
22 |
Correct |
2 ms |
1372 KB |
Output is correct |
23 |
Correct |
3 ms |
1796 KB |
Output is correct |
24 |
Correct |
3 ms |
1624 KB |
Output is correct |
25 |
Correct |
0 ms |
348 KB |
Output is correct |
26 |
Correct |
0 ms |
348 KB |
Output is correct |
27 |
Correct |
5 ms |
1628 KB |
Output is correct |
28 |
Correct |
4 ms |
1496 KB |
Output is correct |
29 |
Correct |
3 ms |
1628 KB |
Output is correct |
30 |
Correct |
3 ms |
1628 KB |
Output is correct |
31 |
Correct |
5 ms |
1628 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
721 ms |
127476 KB |
Output is correct |
5 |
Correct |
307 ms |
98448 KB |
Output is correct |
6 |
Correct |
241 ms |
99668 KB |
Output is correct |
7 |
Correct |
118 ms |
82840 KB |
Output is correct |
8 |
Correct |
86 ms |
68504 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
1 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
1 ms |
708 KB |
Output is correct |
17 |
Correct |
0 ms |
500 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
1 ms |
460 KB |
Output is correct |
20 |
Correct |
1 ms |
348 KB |
Output is correct |
21 |
Correct |
1 ms |
604 KB |
Output is correct |
22 |
Correct |
1 ms |
348 KB |
Output is correct |
23 |
Correct |
1 ms |
344 KB |
Output is correct |
24 |
Correct |
4 ms |
1628 KB |
Output is correct |
25 |
Correct |
4 ms |
1628 KB |
Output is correct |
26 |
Correct |
4 ms |
2136 KB |
Output is correct |
27 |
Correct |
4 ms |
1884 KB |
Output is correct |
28 |
Correct |
3 ms |
1880 KB |
Output is correct |
29 |
Correct |
3 ms |
1628 KB |
Output is correct |
30 |
Correct |
2 ms |
1372 KB |
Output is correct |
31 |
Correct |
3 ms |
1796 KB |
Output is correct |
32 |
Correct |
3 ms |
1624 KB |
Output is correct |
33 |
Correct |
0 ms |
348 KB |
Output is correct |
34 |
Correct |
0 ms |
348 KB |
Output is correct |
35 |
Correct |
5 ms |
1628 KB |
Output is correct |
36 |
Correct |
4 ms |
1496 KB |
Output is correct |
37 |
Correct |
3 ms |
1628 KB |
Output is correct |
38 |
Correct |
3 ms |
1628 KB |
Output is correct |
39 |
Correct |
5 ms |
1628 KB |
Output is correct |
40 |
Correct |
767 ms |
130204 KB |
Output is correct |
41 |
Correct |
352 ms |
101468 KB |
Output is correct |
42 |
Correct |
435 ms |
129724 KB |
Output is correct |
43 |
Correct |
466 ms |
130076 KB |
Output is correct |
44 |
Correct |
272 ms |
101740 KB |
Output is correct |
45 |
Correct |
290 ms |
104380 KB |
Output is correct |
46 |
Correct |
100 ms |
37732 KB |
Output is correct |
47 |
Correct |
308 ms |
108968 KB |
Output is correct |
48 |
Correct |
345 ms |
107312 KB |
Output is correct |