QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#563410 | #4206. Event Hopping | hansiyuan | 0 | 61ms | 29816kb | C++14 | 1.4kb | 2024-09-14 11:25:31 | 2024-09-14 11:25:32 |
Judging History
answer
#include <bits/stdc++.h>
#define pii pair<int,int>
using namespace std;
const int N=1e5+5;
int n,m;
int L[N],R[N],pos[N];
int f0[N][20],g0[N][20];
int f[N][20];
struct nd{int l,r,id;} eve[N];
bool cmp(nd x,nd y){return x.r<y.r;}
int mn=1e9,mnh;
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d%d",&L[i],&R[i]);
eve[i] = {L[i],R[i],i};
}
sort(eve+1,eve+n+1,cmp);
for(int i=1;i<=n;i++){
pos[eve[i].id] = i;
f0[i][0] = eve[i].l;
g0[i][0] = i;
}
for(int j=1;j<=17;j++)
for(int i=1;i+(1<<j)-1<=n;i++){
if(f0[i][j-1] < f0[i+(1<<j-1)][j-1])
f0[i][j]=f0[i][j-1], g0[i][j]=g0[i][j-1];
else
f0[i][j]=f0[i+(1<<j-1)][j-1], g0[i][j]=g0[i+(1<<j-1)][j-1];
}
for(int i=1;i<=n;i++){
int l=1,r=i;
while(l<r){
int mid = (l+r)>>1;
if(eve[mid].r>=eve[i].l) r=mid;
else l=mid+1;
}
int t = log2(i-l+1);
if(f0[l][t] < f0[i-(1<<t)+1][t]) f[i][0]=g0[l][t];
else f[i][0]=g0[i-(1<<t)+1][t];
}
for(int j=1;j<=17;j++)
for(int i=1;i<=n;i++)
f[i][j] = f[f[i][j-1]][j-1];
while(m--){
int s,t;
scanf("%d%d",&s,&t);
if(R[s]>R[t]) {puts("impossible"); continue;}
int ans=0;
int x = pos[t];
for(int j=17;j>=0;j--)
if(eve[f[x][j]].l>L[s]){
ans += (1<<j);
x = f[x][j];
}
if(eve[x].l>L[s]) ans++,x=f[x][0];
if(eve[x].l>L[s]) {puts("impossible"); continue;}
if(x!=pos[s]) ans++,x=pos[s];
printf("%d\n",ans);
}
return 0;
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 10
Accepted
time: 59ms
memory: 29792kb
input:
100000 100000 825913690 825916363 333322014 333324481 302015784 302018251 841002775 841005448 810249910 810252583 803554045 803556718 379590599 379593066 413477311 413479778 304105333 304107800 856802878 856805551 355907399 355909866 365590374 365592841 813775597 813778270 816058339 816061012 383873...
output:
1 impossible 1 impossible impossible impossible 31336 impossible impossible impossible impossible 27166 16274 impossible impossible impossible impossible impossible impossible 21353 17890 impossible impossible impossible impossible impossible impossible impossible impossible impossible impossible 67...
result:
ok 100000 lines
Test #2:
score: 10
Accepted
time: 60ms
memory: 29816kb
input:
100000 100000 389680865 389680885 532001242 532004287 460483812 460491583 691010527 691018298 489353103 489356770 593534107 593537042 509433341 509441112 846177578 846179089 586840272 586848043 834393248 834401019 474044207 474051978 614427322 614435093 574678657 574686428 557256443 557262524 502657...
output:
80801 80800 80800 80799 80799 80799 80798 80798 80798 80798 80797 80797 80797 80797 impossible 80796 80796 80796 80796 impossible 80797 80795 80795 80795 80795 impossible 80796 80796 80794 80794 80794 80794 impossible 80795 80795 80795 80794 80793 80793 80793 impossible 80794 80794 80794 80794 80793...
result:
ok 100000 lines
Test #3:
score: 10
Accepted
time: 36ms
memory: 29684kb
input:
100000 100000 1 2 1 2 5 6 5 6 9 10 9 10 13 14 13 14 17 18 17 18 21 22 21 22 25 26 25 26 29 30 29 30 33 34 33 34 37 38 37 38 41 42 41 42 45 46 45 46 49 50 49 50 53 54 53 54 57 58 57 58 61 62 61 62 65 66 65 66 69 70 69 70 73 74 73 74 77 78 77 78 81 82 81 82 85 86 85 86 89 90 89 90 93 94 93 94 97 98 97...
output:
impossible impossible impossible impossible impossible impossible impossible impossible impossible impossible impossible impossible impossible impossible impossible impossible impossible impossible impossible impossible impossible impossible impossible impossible impossible impossible impossible imp...
result:
ok 100000 lines
Test #4:
score: 10
Accepted
time: 59ms
memory: 29816kb
input:
100000 100000 407280099 407284136 197925316 197929353 463232919 463236956 248771331 248775368 314921613 314925650 454125447 454129484 215159269 215163306 376796712 376800749 343418796 343422833 126014235 126018272 315022538 315026575 242069911 242073948 479849211 479853248 414950399 414954436 254079...
output:
99999 99998 99998 99997 99997 99997 99996 99996 99996 99996 99995 99995 99995 99995 99995 99994 99994 99994 99994 99994 99994 99993 99993 99993 99993 99993 99993 99993 99992 99992 99992 99992 99992 99992 99992 99992 99991 99991 99991 99991 99991 99991 99991 99991 99991 99990 99990 99990 99990 99990 ...
result:
ok 100000 lines
Test #5:
score: 10
Accepted
time: 61ms
memory: 29696kb
input:
100000 100000 861047815 861052922 578273225 578278332 622183211 622188318 822908739 822913846 546318726 546323833 461573168 461578275 480101364 480106471 456455954 456461061 575234560 575239667 464851862 464856969 897159412 897164519 722826860 722831967 755036709 755041816 811213709 811218816 445680...
output:
99999 99997 99995 99993 99991 99989 99987 99985 99983 99981 99979 99977 99975 99973 99971 99969 99967 99965 99963 99961 99959 99957 99955 99953 99951 99949 99947 99945 99943 99941 99939 99937 99935 99933 99931 99929 99927 99925 99923 99921 99919 99917 99915 99913 99911 99909 99907 99905 99903 99901 ...
result:
ok 100000 lines
Test #6:
score: 10
Accepted
time: 48ms
memory: 29620kb
input:
100000 100000 107067593 107068563 375121029 375132523 244489164 244489510 371625987 371628227 63502583 63505678 622119714 622149239 792197805 792202711 692512281 692515198 196552919 196554193 677923903 677926489 680041239 680046357 697562945 697565212 206418851 206420890 410143641 410145269 63943786...
output:
impossible impossible impossible impossible impossible impossible impossible impossible impossible impossible impossible impossible impossible impossible impossible impossible impossible impossible impossible impossible impossible impossible impossible impossible impossible impossible impossible imp...
result:
ok 100000 lines
Test #7:
score: 10
Accepted
time: 1ms
memory: 12140kb
input:
8 5 1 2 3 4 1 5 6 7 5 10 10 20 15 20 999999999 1000000000 1 6 1 7 2 4 3 3 5 8
output:
3 4 impossible 0 impossible
result:
ok 5 lines
Test #8:
score: 10
Accepted
time: 53ms
memory: 29800kb
input:
100000 100000 432053319 432056406 486393780 486396867 318945639 318948726 557737437 557740524 505903620 505906707 312861162 312864249 530084091 530087178 378401259 378404346 590749815 590752902 384158514 384161601 397824663 397827750 305937021 305940108 418238994 418242081 311718972 311722059 421174...
output:
99999 99999 99999 99999 99999 99999 99999 99999 99999 99999 99999 99999 99999 99999 99999 99999 99999 99999 99999 99999 99999 99999 99999 99999 99999 99999 99999 99999 99999 99999 99999 99999 99999 99999 99999 99999 99999 99999 99999 99999 99999 99999 99999 99999 99999 99999 99999 99999 99999 99999 ...
result:
ok 100000 lines
Test #9:
score: 10
Accepted
time: 57ms
memory: 29736kb
input:
100000 100000 460767811 460773658 363280780 363286627 318744181 318750028 587618476 587624323 349815139 349820986 654104713 654110560 522640765 522646612 667874398 667880245 722245651 722251498 442864297 442870144 522664153 522670000 660805375 660811222 710639356 710645203 484196740 484202587 355358...
output:
77828 77828 77829 77828 77829 77827 77827 77829 77827 77826 77826 77828 77827 77826 77825 77825 77827 77826 77826 77825 impossible 77824 77826 77825 77825 77825 impossible 77824 77824 77825 77824 77824 77824 impossible 77824 77823 77823 77825 77823 77823 77823 impossible 77824 77823 77822 77823 7782...
result:
ok 100000 lines
Test #10:
score: 0
Wrong Answer
time: 45ms
memory: 29656kb
input:
100000 100000 639515864 639521231 667143094 667144538 647258206 647258690 462233258 462234230 475801547 475802613 524127311 524128428 543287190 543289381 535841282 535843238 585211823 585213845 734658645 734658899 537776171 537783441 730349191 730354503 616233528 616234443 679161417 679162801 660817...
output:
1 1 impossible 1 impossible impossible 1 impossible impossible impossible 1 impossible impossible impossible impossible 1 impossible impossible impossible impossible impossible 1 impossible impossible impossible impossible impossible impossible 1 impossible impossible impossible impossible impossibl...
result:
wrong answer 3rd lines differ - expected: '2', found: 'impossible'
Subtask #2:
score: 0
Wrong Answer
Test #13:
score: 0
Wrong Answer
time: 2ms
memory: 12040kb
input:
1000 100 67878298 387720407 270457472 922959000 286470357 618323410 260791474 282940414 301337446 553875076 478221503 724555102 380447228 437131400 191801427 465825895 366088873 431222136 49483883 103442781 699926238 720636919 253150351 291688158 411085513 727726933 444078045 496386017 420626857 822...
output:
1 2 2 impossible 1 2 1 2 impossible 2 2 impossible impossible impossible 2 impossible impossible impossible impossible impossible 2 impossible 2 impossible 1 1 impossible 1 1 2 1 impossible 2 impossible 2 impossible 1 2 impossible impossible impossible 2 2 impossible impossible 2 2 impossible imposs...
result:
wrong answer 15th lines differ - expected: '1', found: '2'
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Skipped
Dependency #2:
0%
Subtask #5:
score: 0
Wrong Answer
Test #35:
score: 0
Wrong Answer
time: 49ms
memory: 29764kb
input:
100000 100000 903318459 905410836 903528407 905653109 925180437 927048927 473524826 475597377 362562616 364539688 644980844 646918450 242583398 244653279 506338025 508361063 481496693 483530832 970053326 972147109 794840350 796900045 130664210 132709680 634100524 636336820 844429264 846504591 652483...
output:
500 501 500 501 501 500 501 501 501 500 501 501 501 501 500 501 501 501 501 501 500 501 501 501 501 501 501 500 501 501 501 501 501 501 501 500 501 501 501 501 501 501 501 501 500 501 501 501 501 501 501 501 501 501 500 501 501 501 501 501 501 501 501 501 501 500 501 501 501 501 501 501 501 501 501 ...
result:
wrong answer 2nd lines differ - expected: '500', found: '501'
Subtask #6:
score: 0
Skipped
Dependency #1:
0%