#include <bits/stdc++.h>
using namespace std;
vector<int> graph[200001];
int to[200001];
int rv[200001];
struct maxtree {
int tree[200001];
// int lazy[200001];
void build(int n, int a, int b) {
if (a == b) {
tree[n] = to[a];
return;
}
build(2*n,a,(a+b)/2);
build(2*n+1,(a+b)/2+1,b);
tree[n] = max(tree[2*n],tree[2*n+1]);
return;
}
// void upd(int n, int a, int b, int x, int y, int val) {
// if (lazy[n] != 0) {
// // printf("[%d,%d]: %lld\n",a,b,lazy[n]);
// tree[n] += lazy[n];
// if (a != b) {
// lazy[2*n] += lazy[n];
// lazy[2*n+1] += lazy[n];
// }
// lazy[n] = 0;
// }
// if (a > b || b < x || y < a) {
// return;
// }
// if (x <= a && b <= y) {
// tree[n] += val;
// // printf("!!!!!%d %d => %lld + %lld = %lld\n",a,b,tree[n]-val,val,tree[n]);
// if (a != b) {
// lazy[2*n] += val;
// lazy[2*n+1] += val;
// }
// return;
// }
// upd(2*n,a,(a+b)/2,x,y,val);
// upd(2*n+1,(a+b)/2+1,b,x,y,val);
// tree[n] = max(tree[2*n],tree[2*n+1]);
// return;
// }
int qry(int n, int a, int b, int x, int y) {
// if (lazy[n] != 0) {
// // printf("[%d,%d]: %lld\n",a,b,lazy[n]);
// tree[n] += lazy[n];
// if (a != b) {
// lazy[2*n] += lazy[n];
// lazy[2*n+1] += lazy[n];
// }
// lazy[n] = 0;
// }
if (a > b || b < x || y < a) {
return -1;
}
if (x <= a && b <= y) {
// printf("%d %d %lld!\n",a,b,tree[n]);
return tree[n];
}
return max(qry(2*n,a,(a+b)/2,x,y),qry(2*n+1,(a+b)/2+1,b,x,y));
}
};
struct mintree {
int tree[200001];
// int lazy[200001];
void build(int n, int a, int b) {
if (a == b) {
tree[n] = rv[a];
return;
}
build(2*n,a,(a+b)/2);
build(2*n+1,(a+b)/2+1,b);
tree[n] = min(tree[2*n],tree[2*n+1]);
return;
}
// void upd(int n, int a, int b, int x, int y, int val) {
// if (lazy[n] != 0) {
// // printf("[%d,%d]: %lld\n",a,b,lazy[n]);
// tree[n] += lazy[n];
// if (a != b) {
// lazy[2*n] += lazy[n];
// lazy[2*n+1] += lazy[n];
// }
// lazy[n] = 0;
// }
// if (a > b || b < x || y < a) {
// return;
// }
// if (x <= a && b <= y) {
// tree[n] += val;
// // printf("!!!!!%d %d => %lld + %lld = %lld\n",a,b,tree[n]-val,val,tree[n]);
// if (a != b) {
// lazy[2*n] += val;
// lazy[2*n+1] += val;
// }
// return;
// }
// upd(2*n,a,(a+b)/2,x,y,val);
// upd(2*n+1,(a+b)/2+1,b,x,y,val);
// tree[n] = min(tree[2*n],tree[2*n+1]);
// return;
// }
int qry(int n, int a, int b, int x, int y) {
// if (lazy[n] != 0) {
// // printf("[%d,%d]: %lld\n",a,b,lazy[n]);
// tree[n] += lazy[n];
// if (a != b) {
// lazy[2*n] += lazy[n];
// lazy[2*n+1] += lazy[n];
// }
// lazy[n] = 0;
// }
if (a > b || b < x || y < a) {
return 1e9;
}
if (x <= a && b <= y) {
// printf("%d %d %lld!\n",a,b,tree[n]);
return tree[n];
}
return min(qry(2*n,a,(a+b)/2,x,y),qry(2*n+1,(a+b)/2+1,b,x,y));
}
};
mintree tree1;
maxtree tree2;
int main() {
int n;
scanf("%d",&n);
int max1 = 0;
for (int i = 1; i <= n; ++i) {
int l, r;
scanf("%d%d",&l,&r);
to[i] = r;
rv[i] = l;
}
tree1.build(1,1,n);
tree2.build(1,1,n);
int q;
scanf("%d",&q);
for (int qi = 0; qi < q; ++qi) {
int x;
scanf("%d",&x);
int l = 1e9;
int r = -1e9;
int ans = 0;
int cnt = 0;
while (++cnt <= n && (l != 1 || r != n)) {
// printf("%d %d\n",l,r);
int nl = tree1.qry(1,1,n,l,r);
int nr = tree2.qry(1,1,n,l,r);
l = nl;
r = nr;
++ans;
}
if (cnt > n)printf("-1\n");
else printf("%d\n",ans);
}
return 0;
}
Compilation message
passport.cpp: In function 'int main()':
passport.cpp:136:6: warning: unused variable 'max1' [-Wunused-variable]
136 | int max1 = 0;
| ^~~~
passport.cpp:135:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
135 | scanf("%d",&n);
| ~~~~~^~~~~~~~~
passport.cpp:139:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
139 | scanf("%d%d",&l,&r);
| ~~~~~^~~~~~~~~~~~~~
passport.cpp:146:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
146 | scanf("%d",&q);
| ~~~~~^~~~~~~~~
passport.cpp:149:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
149 | scanf("%d",&x);
| ~~~~~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
