QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#414278 | #6334. Passport | Rafi22# | 22 | 264ms | 67872kb | C++14 | 2.2kb | 2024-05-18 19:43:24 | 2024-05-18 19:43:25 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
#define ll long long
#define ld long double
#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
using namespace std;
int inf=1000000007;
ll infl=1000000000000000007;
int mod=998244353;
const int N=200007,pot=1<<18;
pair<int,int>seg[2*pot+7];
pair<int,int>que(int v,int a,int b,int l,int r)
{
if(a<=l&&b>=r) return seg[v];
if(r<a||l>b) return {inf,0};
return min(que(2*v,a,b,l,(l+r)/2),que(2*v+1,a,b,(l+r)/2+1,r));
}
pair<int,int>seg1[2*pot+7];
pair<int,int>que1(int v,int a,int b,int l,int r)
{
if(a<=l&&b>=r) return seg1[v];
if(r<a||l>b) return {-inf,0};
return max(que1(2*v,a,b,l,(l+r)/2),que1(2*v+1,a,b,(l+r)/2+1,r));
}
vector<int>G[N];
bool odw[N];
int l[N],r[N];
int L[N],R[N];
int A[N],B[N];
vector<int>X[N],Y[N];
int ans[N];
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
A[i]=inf;
B[i]=inf;
}
for(int i=1;i<=n;i++)
{
cin>>l[i]>>r[i];
if(l[i]==1) A[i]=0;
if(r[i]==n) B[i]=0;
X[l[i]].pb(i);
Y[r[i]].pb(i);
seg[i+pot-1]={l[i],i};
seg1[i+pot-1]={r[i],i};
}
for(int i=n+1;i<=pot;i++)
{
seg[i+pot-1]={inf,i};
seg1[i+pot-1]={-inf,i};
}
for(int i=pot-1;i>0;i--)
{
seg[i]=min(seg[2*i],seg[2*i+1]);
seg1[i]=max(seg1[2*i],seg1[2*i+1]);
}
for(int i=1;i<=n;i++)
{
L[i]=que(1,l[i],r[i],1,pot).nd;
R[i]=que1(1,l[i],r[i],1,pot).nd;
G[L[i]].pb(i);
G[R[i]].pb(i);
}
for(int i=2;i<=n;i++)
{
for(auto j:X[i]) A[j]=A[L[j]]+1;
}
for(int i=n-1;i>0;i--)
{
for(auto j:Y[i]) B[j]=B[R[j]]+1;
}
priority_queue<pair<int,int>>Q;
for(int i=1;i<=n;i++)
{
ans[i]=A[i]+B[i]+1;
Q.push({-ans[i],i});
}
while(sz(Q)>0)
{
int v=Q.top().nd;
Q.pop();
if(odw[v]) continue;
odw[v]=1;
for(auto u:G[v])
{
if(ans[v]+1<ans[u])
{
ans[u]=ans[v]+1;
Q.push({-ans[u],u});
}
}
}
int q,x;
cin>>q;
while(q--)
{
cin>>x;
if(ans[x]>n) cout<<-1<<endl;
else cout<<ans[x]<<endl;
}
return 0;
}
詳細信息
Subtask #1:
score: 6
Accepted
Test #1:
score: 6
Accepted
time: 3ms
memory: 43808kb
input:
2 1 1 1 2 1 1
output:
-1
result:
ok single line: '-1'
Test #2:
score: 6
Accepted
time: 3ms
memory: 44960kb
input:
2 1 2 2 2 1 1
output:
1
result:
ok single line: '1'
Test #3:
score: 6
Accepted
time: 264ms
memory: 60932kb
input:
196001 1 408 2 37822 1 1221 1 160899 4 62751 3 21706 2 4118 8 70696 8 4916 3 24286 9 443 8 171744 11 170980 7 3541 12 16428 8 71164 1 186827 11 234 2 23141 4 17143 21 9522 10 24 19 15936 3 15884 17 426 14 3188 17 168317 4 1560 25 35 16 39439 21 122 4 17507 8 97645 11 824 25 59856 30 9265 7 151420 37...
output:
3
result:
ok single line: '3'
Test #4:
score: 6
Accepted
time: 163ms
memory: 64284kb
input:
198001 1 17 1 19 1 4 2 20 3 15 6 10 1 20 3 9 3 9 10 19 6 27 8 29 12 24 3 23 8 23 16 19 11 23 1 19 13 30 19 32 4 28 15 33 23 33 8 36 16 30 23 40 11 42 27 34 20 30 21 36 31 39 30 35 32 33 29 48 27 43 33 41 25 53 28 51 29 56 37 55 35 54 36 52 35 44 31 58 36 54 42 56 47 49 41 59 37 64 44 50 34 55 41 56 ...
output:
15219
result:
ok single line: '15219'
Test #5:
score: 6
Accepted
time: 123ms
memory: 67872kb
input:
200000 1 2 1 3 2 4 3 5 4 6 5 7 6 8 7 9 8 10 9 11 10 12 11 13 12 14 13 15 14 16 15 17 16 18 17 19 18 20 19 21 20 22 21 23 22 24 23 25 24 26 25 27 26 28 27 29 28 30 29 31 30 32 31 33 32 34 33 35 34 36 35 37 36 38 37 39 38 40 39 41 40 42 41 43 42 44 43 45 44 46 45 47 46 48 47 49 48 50 49 51 50 52 51 53...
output:
199999
result:
ok single line: '199999'
Test #6:
score: 6
Accepted
time: 69ms
memory: 55440kb
input:
195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195000 1 195...
output:
1
result:
ok single line: '1'
Test #7:
score: 6
Accepted
time: 87ms
memory: 54584kb
input:
156789 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 78394 1 783...
output:
-1
result:
ok single line: '-1'
Subtask #2:
score: 16
Accepted
Test #8:
score: 16
Accepted
time: 3ms
memory: 43628kb
input:
2 1 1 1 2 1 2
output:
1
result:
ok single line: '1'
Test #9:
score: 16
Accepted
time: 3ms
memory: 44252kb
input:
2 1 2 2 2 1 2
output:
-1
result:
ok single line: '-1'
Test #10:
score: 16
Accepted
time: 0ms
memory: 43596kb
input:
6 1 1 2 2 1 3 3 5 5 6 1 6 1 4
output:
3
result:
ok single line: '3'
Test #11:
score: 16
Accepted
time: 0ms
memory: 45188kb
input:
9 1 1 2 2 3 3 1 4 2 8 5 7 4 9 8 8 9 9 1 6
output:
3
result:
ok single line: '3'
Test #12:
score: 16
Accepted
time: 7ms
memory: 43540kb
input:
9 1 1 2 2 3 3 1 4 2 8 4 9 5 7 8 8 9 9 1 7
output:
3
result:
ok single line: '3'
Test #13:
score: 16
Accepted
time: 3ms
memory: 43612kb
input:
10 1 1 2 2 3 3 2 10 1 6 3 8 1 8 6 8 3 9 10 10 1 4
output:
2
result:
ok single line: '2'
Test #14:
score: 16
Accepted
time: 3ms
memory: 43636kb
input:
285 1 13 1 16 3 16 3 25 3 94 5 100 2 92 7 10 9 10 1 270 11 11 9 93 5 43 4 115 11 15 10 66 16 20 16 58 16 22 3 124 15 31 1 59 23 23 24 24 19 28 22 126 27 27 20 89 16 218 24 42 10 135 21 156 8 187 27 265 34 35 34 41 15 233 33 107 38 44 5 284 41 42 13 169 33 51 5 81 41 89 44 52 43 50 23 86 42 62 4 95 4...
output:
4
result:
ok single line: '4'
Test #15:
score: 16
Accepted
time: 3ms
memory: 45220kb
input:
296 1 1 1 7 2 6 2 12 4 5 5 8 1 13 6 13 5 17 2 13 3 13 11 17 13 20 10 21 9 16 11 22 12 19 14 19 14 19 12 28 14 23 20 25 15 23 18 31 20 32 20 26 21 33 24 32 22 37 29 35 29 36 31 38 25 34 32 35 34 39 36 37 29 42 36 46 39 43 40 44 33 46 41 48 43 51 39 45 44 47 43 50 41 53 44 52 43 52 45 51 47 58 48 59 5...
output:
49
result:
ok single line: '49'
Test #16:
score: 16
Accepted
time: 0ms
memory: 44896kb
input:
300 1 300 1 300 1 300 2 300 1 299 4 299 5 296 6 298 7 294 7 295 9 292 9 291 11 290 12 291 12 292 13 287 14 286 16 285 17 284 18 284 19 282 20 281 21 281 21 280 21 278 24 277 24 276 26 275 27 274 27 273 29 287 30 271 28 273 27 269 33 268 34 268 31 284 30 265 37 265 38 264 38 264 40 261 40 260 40 260 ...
output:
10
result:
ok single line: '10'
Test #17:
score: 16
Accepted
time: 3ms
memory: 43520kb
input:
287 1 287 1 287 1 285 1 285 2 284 4 282 5 281 1 280 5 279 8 279 9 277 10 276 11 275 1 275 7 274 14 272 15 271 16 270 17 270 18 268 15 268 1 266 19 266 22 264 22 263 22 263 25 261 26 260 26 263 24 259 29 257 29 258 31 257 31 254 33 253 14 255 34 252 31 250 33 250 35 248 32 247 39 246 40 246 33 244 43...
output:
7
result:
ok single line: '7'
Test #18:
score: 16
Accepted
time: 3ms
memory: 44900kb
input:
300 1 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 ...
output:
298
result:
ok single line: '298'
Subtask #3:
score: 0
Wrong Answer
Test #19:
score: 24
Accepted
time: 4ms
memory: 44048kb
input:
2337 1 3 2 77 1 1397 2 222 3 62 6 1896 7 10 6 950 9 9 10 16 11 455 9 588 13 16 7 1245 9 1342 8 1727 7 122 11 653 9 1094 2 57 11 81 19 1290 6 1584 16 79 14 215 21 61 27 27 16 1458 16 198 26 180 31 31 11 240 33 36 11 121 34 1542 9 1752 14 456 36 43 36 2244 40 40 4 517 42 662 31 1350 33 162 30 843 28 1...
output:
4
result:
ok single line: '4'
Test #20:
score: 0
Wrong Answer
time: 4ms
memory: 43908kb
input:
2486 1 12 2 8 1 7 3 12 2 11 3 15 1 8 4 11 9 15 3 21 11 13 4 15 9 21 9 19 5 15 8 20 8 25 16 24 11 29 11 23 18 23 14 32 17 24 13 27 15 30 21 34 16 29 20 35 19 32 29 34 20 39 21 43 29 40 28 43 26 44 31 45 28 43 35 38 30 40 37 46 40 43 42 42 42 45 43 54 39 51 40 51 45 54 46 57 39 53 47 53 47 54 41 59 49...
output:
315
result:
wrong answer 1st lines differ - expected: '314', found: '315'
Subtask #4:
score: 0
Wrong Answer
Test #28:
score: 0
Wrong Answer
time: 8ms
memory: 44208kb
input:
2419 1 883 1 29 3 41 4 2201 1 808 6 45 7 1456 6 134 6 1372 1 1776 4 441 7 208 5 28 4 604 7 56 9 617 8 2115 15 60 13 456 10 2071 18 23 18 39 5 39 21 35 4 75 25 44 24 640 21 30 4 860 30 31 18 78 32 779 1 927 33 34 19 59 34 181 21 502 23 155 39 39 2 254 30 641 42 50 10 2000 41 2220 18 632 35 48 27 905 ...
output:
3 3 4 3 3 3 3 3 3 2 4 3 4 4 3 3 3 4 4 3 4 4 4 4 4 4 4 5 4 5 4 4 3 4 4 4 4 4 -1 4 4 4 3 3 4 4 4 4 3 4 4 3 -1 3 4 4 4 3 -1 4 4 4 3 4 4 4 4 4 4 3 3 4 5 4 3 3 4 4 3 4 4 3 4 3 4 4 -1 -1 3 4 4 3 4 4 3 4 3 4 5 4 4 4 4 3 4 4 4 3 4 5 4 4 4 4 4 3 4 4 4 4 4 4 4 3 4 4 4 -1 4 3 3 3 4 4 4 5 4 4 3 4 4 5 -1 4 4 4 4...
result:
wrong answer 3rd lines differ - expected: '3', found: '4'
Subtask #5:
score: 0
Wrong Answer
Test #33:
score: 0
Wrong Answer
time: 260ms
memory: 61216kb
input:
196830 1 67357 2 183304 3 23390 4 54 1 145887 3 27807 3 12376 1 1013 3 113274 3 191874 6 23342 9 2113 13 94245 3 141449 10 1727 3 51 17 99028 6 193803 8 7452 6 121537 9 23658 18 611 6 4756 4 5141 8 8547 8 66922 13 7021 9 72 3 53043 16 167381 2 15530 5 192 33 33 9 92655 10 36182 20 19992 36 24454 1 6...
output:
3 3 4 4 3 4 4 3 4 3 4 4 4 4 4 4 4 3 4 4 4 4 4 4 4 4 4 4 4 3 4 4 -1 4 4 4 4 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 3 3 3 4 3 4 4 4 4 4 4 3 3 3 3 4 4 4 3 3 4 3 3 4 4 3 3 3 4 4 4 4 4 4 3 4 3 4 3 3 4 3 3 3 4 3 4 3 3 -1 4 3 4 3 3 3 3 3 4 4 3 4 4 4 4 3 4 -1 3 4 3 4 4 3 3 3 4 3 3 3 4 4 3 4 4 4 3 3 3 3 4 3 4 3 3 3 3...
result:
wrong answer 3rd lines differ - expected: '3', found: '4'