| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1069615 |
2024-08-22T07:12:03 Z |
김은성(#11131) |
Passport (JOI23_passport) |
C++17 |
|
1 ms |
2396 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll KEY = 1.557e8;
const int INF = 1.557e8;
unordered_map<ll, int> memo;
int lb[200009], rb[200009];
int n, minl[1<<19], maxr[1<<19];
void settree(int v, int l, int r){
if(l==r){
minl[v] = lb[l];
maxr[v] = rb[l];
}
else{
int mid = (l+r)/2;
settree(2*v, l, mid);
settree(2*v+1, mid+1, r);
minl[v] = min(minl[2*v], minl[2*v+1]);
maxr[v] = max(maxr[2*v], maxr[2*v+1]);
}
}
int minquery(int v, int l, int r, int s, int e){
if(e<l || r<s)
return INF;
if(s<=l && r<=e)
return minl[v];
int mid = (l+r)/2;
return min(minquery(2*v, l, mid, s, e), minquery(2*v+1, mid+1, r, s, e));
}
int maxquery(int v, int l, int r, int s, int e){
if(e<l || r<s)
return -1;
if(s<=l && r<=e)
return maxr[v];
int mid = (l+r)/2;
return max(maxquery(2*v, l, mid, s, e), maxquery(2*v+1, mid+1, r, s, e));
}
int solve(int l, int r){
if(l==1 && r==n)
return 0;
auto it = memo.find(l * KEY + r);
if(it != memo.end())
return it->second;
int pl = minquery(1, 1, n, l, r), pr = maxquery(1, 1, n, l, r);
int ret = INF;
if(pl < l)
ret = min(ret, solve(pl, r) + 1);
if(pr < r)
ret = min(ret, solve(l, pr) + 1);
for(int i=l; i<=r; i++){
if(lb[i] < l && rb[i] > r)
ret = min(ret, solve(lb[i], rb[i]) + 1);
}
return memo[l*KEY + r] = ret;
}
int main(){
int q, t, i, j, k, x;
scanf("%d", &n);
for(i=1; i<=n; i++){
scanf("%d %d", &lb[i], &rb[i]);
}
scanf("%d", &q);
while(q--){
scanf("%d", &x);
int ans = solve(lb[x], rb[x]) + 1;
if(ans >= INF/2)
ans = -1;
printf("%d\n", ans);
}
return 0;
}
Compilation message
passport.cpp: In function 'int main()':
passport.cpp:57:9: warning: unused variable 't' [-Wunused-variable]
57 | int q, t, i, j, k, x;
| ^
passport.cpp:57:15: warning: unused variable 'j' [-Wunused-variable]
57 | int q, t, i, j, k, x;
| ^
passport.cpp:57:18: warning: unused variable 'k' [-Wunused-variable]
57 | int q, t, i, j, k, x;
| ^
passport.cpp:58:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
58 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
passport.cpp:60:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
60 | scanf("%d %d", &lb[i], &rb[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
passport.cpp:62:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
62 | scanf("%d", &q);
| ~~~~~^~~~~~~~~~
passport.cpp:64:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
64 | scanf("%d", &x);
| ~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
