| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1069867 |
2024-08-22T09:29:48 Z |
김은성(#11131) |
Passport (JOI23_passport) |
C++17 |
|
2000 ms |
90208 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];
int tree[1<<19];
void update(int v, int l, int r, int idx, int val){
if(l==r)
tree[v] = val;
else{
int mid = (l+r)/2;
if(idx <= mid)
update(2*v, l, mid, idx, val);
else
update(2*v+1, mid+1, r, idx, val);
tree[v] = min(tree[2*v], tree[2*v+1]);
}
}
int rangemin(int v, int l, int r, int s, int e){
if(e<l || r<s)
return INF;
if(s<=l && r<=e)
return tree[v];
int mid = (l+r)/2;
return min(rangemin(2*v, l, mid, s, e), rangemin(2*v+1, mid+1, r, s, e));
}
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(((ll)l<<30) + r);
if(it != memo.end())
return it->second;
int pl = minquery(1, 1, n, l, r), pr = maxquery(1, 1, n, l, r);
//printf("l=%d r=%d pl=%d pr=%d\n",l, r, pl,pr);
int ret = INF;
if(pl < l && pr > r){
ret = min(ret, solve(pl, pr) + 2);
ret = min(ret, rangemin(1, 1, n, l, r));
}
else if(pl < l){
int now = 0;
while(pr <= r){
if(pl >= l){
return memo[((ll)l<<30) +r] = INF;
}
l = pl;
pl = minquery(1, 1, n, l, r), pr = maxquery(1, 1, n, l, r);
now++;
}
ret = min(ret, solve(pl, r)+now);
}
else if(pr > r)
ret = min(ret, solve(l, pr) + 1);
return memo[((ll)l<<30) +r] = ret;
}
int ans[200009];
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]);
}
memset(tree, 127, sizeof(tree));
settree(1,1, n);
scanf("%d", &q);
vector<int> vec;
for(i=1; i<=n; i++)
vec.push_back(i);
sort(vec.begin(), vec.end(), [](int &u, int &v){return rb[v]-lb[v] < rb[u]-lb[u];});
for(int u: vec){
ans[u] = solve(lb[u], rb[u]) + 1;
update(1, 1, n, u, ans[u]);
}
while(q--){
scanf("%d", &x);
if(ans[x] >= INF/2)
ans[x] = -1;
printf("%d\n", ans[x]);
}
return 0;
}
Compilation message
passport.cpp: In function 'int main()':
passport.cpp:90:9: warning: unused variable 't' [-Wunused-variable]
90 | int q, t, i, j, k, x;
| ^
passport.cpp:90:15: warning: unused variable 'j' [-Wunused-variable]
90 | int q, t, i, j, k, x;
| ^
passport.cpp:90:18: warning: unused variable 'k' [-Wunused-variable]
90 | int q, t, i, j, k, x;
| ^
passport.cpp:91:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
91 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
passport.cpp:93:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
93 | scanf("%d %d", &lb[i], &rb[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
passport.cpp:97:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
97 | scanf("%d", &q);
| ~~~~~^~~~~~~~~~
passport.cpp:107:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
107 | scanf("%d", &x);
| ~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 2 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 3 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 4 |
Correct |
281 ms |
19084 KB |
Output is correct |
| 5 |
Execution timed out |
2054 ms |
90208 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
8540 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
8540 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
8540 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 2 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 3 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 4 |
Correct |
281 ms |
19084 KB |
Output is correct |
| 5 |
Execution timed out |
2054 ms |
90208 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
