QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#89950 | #4151. 拦截导弹 | Alex10086 | 100 ✓ | 193ms | 4772kb | C++14 | 2.8kb | 2023-03-21 20:40:18 | 2023-03-21 20:40:22 |
Judging History
answer
#include<cstdio>
#include<algorithm>
using namespace std;
typedef double db;const int N=1e6+10;
struct data{int h;int v;int p;int ma;db ca;}a[2][N];int n;bool tr;//不要取反!
inline bool cmp1(const data& a,const data& b){if(tr)return a.h>b.h;else return a.h<b.h;}
inline bool cmp2(const data& a,const data& b){if(tr)return a.v>b.v;else return a.v<b.v;}
inline bool cmp3(const data& a,const data& b){if(tr)return a.p<b.p;else return a.p>b.p;}
inline bool cmp4(const data& a,const data& b){return a.v==b.v;}
struct treearray//树状数组,记得再维护一个方案数
{
int ma[2*N];db ca[2*N];
inline void c(int x,int t,db c)//修改
{for(;x<=n;x+=x&(-x)){if(ma[x]==t){ca[x]+=c;}else if(ma[x]<t){ca[x]=c;ma[x]=t;}}}
inline void d(int x){for(;x<=n;x+=x&(-x)){ma[x]=0;ca[x]=0;}}//删除
inline void q(int x,int& m,db& c)//询问(其实这里不是故意叫cdq的)
{for(;x>0;x-=x&(-x)){if(ma[x]==m){c+=ca[x];}else if(m<ma[x]){c=ca[x];m=ma[x];}}}
}ta;int rk[2][N];
inline void solve(int l,int r,int t)//分治
{
if(r-l==1){return;}int mid=(l+r)/2;
solve(l,mid,t);sort(a[t]+mid+1,a[t]+r+1,cmp1);int p=l+1;
for(int i=mid+1;i<=r;i++)//维护双指针 ,记得判相等
{
for(;(cmp1(a[t][p],a[t][i])||a[t][p].h==a[t][i].h)&&p<=mid;p++)
{ta.c(a[t][p].v,a[t][p].ma,a[t][p].ca);}db c=0;int m=0;ta.q(a[t][i].v,m,c);
if(a[t][i].ma<m+1){a[t][i].ma=m+1;a[t][i].ca=c;}else if(a[t][i].ma==m+1){a[t][i].ca+=c;}
}for(int i=l+1;i<=mid;i++){ta.d(a[t][i].v);}//记得回撤
sort(a[t]+mid,a[t]+r+1,cmp3);solve(mid,r,t);//这里注意,大力sorth后要sort回来,你后边还没解决呢
sort(a[t]+l+1,a[t]+r+1,cmp1);//最后按h排好序
}
inline void ih(int t)//这里是离散化
{
sort(a[t]+1,a[t]+n+1,cmp2);rk[t][1]=1;//这样两次树状数组都可以只查前缀了
for(int i=2;i<=n;i++){rk[t][i]=(cmp4(a[t][i],a[t][i-1]))?rk[t][i-1]:i;}
for(int i=1;i<=n;i++){a[t][i].v=rk[t][i];}sort(a[t]+1,a[t]+n+1,cmp3);
for(int i=1;i<=n;i++){a[t][i].ma=1;a[t][i].ca=1;}//赋dp初值
}int len;db ans;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&a[0][i].h,&a[0][i].v);a[0][i].p=i;
a[1][i].h=a[0][i].h;a[1][i].v=a[0][i].v;a[1][i].p=i;
}ih(0);solve(0,n,0);tr=1;ih(1);solve(0,n,1);tr=1;//两边cdq
sort(a[0]+1,a[0]+n+1,cmp3);sort(a[1]+1,a[1]+n+1,cmp3);//统计答案要sort回来
for(int i=1;i<=n;i++){len=max(len,a[0][i].ma);}printf("%d\n",len);
for(int i=1;i<=n;i++){if(a[0][i].ma==len){ans+=a[0][i].ca;}}
for(int i=1;i<=n;i++)//然后强行计算期望就好了
{
if(a[0][i].ma+a[1][i].ma-1==len){printf("%.5lf ",(a[0][i].ca*a[1][i].ca)/ans);}
else {printf("0.00000 ");}
}return 0;//拜拜程序~
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 5
Accepted
time: 2ms
memory: 1740kb
input:
955 736740752 79345639 558212775 79345639 593986004 79345639 747075168 79345639 68546702 79345639 98152103 79345639 311401753 79345639 674385237 79345639 631265401 79345639 607465477 79345639 971808535 79345639 627715320 79345639 657182569 79345639 618524434 79345639 46421370 79345639 877444310 7934...
output:
59 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 1.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 1.00000 0.00000 0.00000 0.00000 0.00000 1.00000 0.00000 0.00000 0.00000 0.00000 1.00000 0.00000 0.00000 0.00000 0.33333 0...
result:
points 1.0 First Answer Correct, Second Line Correct
Test #2:
score: 5
Accepted
time: 2ms
memory: 1648kb
input:
758 539620657 327294404 189125385 364084538 860172671 430739286 192505007 230794454 221630001 716266879 395939145 779596830 332246835 459559333 54205431 887536294 672959112 607045830 476318930 6592793 522361820 598184309 522361820 134330396 571429541 485652193 892033454 18146976 52052052 173151366 4...
output:
19 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0...
result:
points 1.0 First Answer Correct, Second Line Correct
Test #3:
score: 5
Accepted
time: 2ms
memory: 1744kb
input:
553 834647309 358010781 445612170 847638585 43049893 894351683 881052905 2552696 83265414 499028382 143910149 336742029 403990342 165592090 621695299 203802820 864957104 157713568 405969647 499028382 258455690 895345510 617189741 643979908 908667872 9416592 417701662 676869074 807035700 19117578 258...
output:
16 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0...
result:
points 1.0 First Answer Correct, Second Line Correct
Test #4:
score: 5
Accepted
time: 0ms
memory: 1640kb
input:
944 93 715 874 125 998 388 395 949 687 415 995 430 742 782 924 63 445 260 630 49 354 769 259 248 922 780 602 128 128 212 353 794 640 936 79 14 145 160 617 803 314 507 99 774 828 906 825 752 873 653 190 867 419 980 444 677 184 961 853 782 956 397 51 935 423 199 451 747 337 996 527 347 299 627 571 252...
output:
19 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.58065 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.29032 0.58065 0.29032 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0...
result:
points 1.0 First Answer Correct, Second Line Correct
Test #5:
score: 5
Accepted
time: 3ms
memory: 1636kb
input:
934 358 640 943 643 781 752 303 560 21 852 435 429 340 556 31 40 677 720 536 859 904 111 767 206 576 371 216 761 964 220 668 258 70 884 556 516 696 636 678 529 137 701 405 200 202 529 508 914 853 138 227 74 976 435 405 404 422 86 345 312 23 222 184 398 602 551 887 515 536 690 565 197 154 541 78 572 ...
output:
18 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0...
result:
points 1.0 First Answer Correct, Second Line Correct
Test #6:
score: 5
Accepted
time: 0ms
memory: 1744kb
input:
807 476 922 368 922 546 922 459 922 97 922 862 922 755 922 291 922 279 922 157 922 572 922 355 922 430 922 424 922 717 922 223 922 524 922 709 922 903 922 447 922 865 922 110 922 604 922 216 922 426 922 753 922 101 922 866 922 42 922 928 922 283 922 192 922 540 922 26 922 814 922 619 922 523 922 792...
output:
51 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.40000 0.00000 0.20000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.20000 0.00000 0.60000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0...
result:
points 1.0 First Answer Correct, Second Line Correct
Test #7:
score: 5
Accepted
time: 177ms
memory: 4392kb
input:
42482 934 713 76 308 102 13 784 121 907 784 98 368 614 334 543 501 190 33 888 248 162 909 620 233 272 545 248 608 334 226 812 395 927 103 888 412 192 824 158 738 979 888 137 319 980 645 743 969 570 397 763 533 768 396 62 969 493 867 655 616 585 323 408 868 649 314 979 695 20 997 573 386 198 383 290 ...
output:
81 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0...
result:
points 1.0 First Answer Correct, Second Line Correct
Test #8:
score: 5
Accepted
time: 193ms
memory: 4772kb
input:
48317 952 421 732 645 56 376 200 961 394 863 151 967 512 257 966 72 835 696 30 950 883 649 677 395 238 896 854 991 884 279 842 23 810 561 367 954 405 754 192 565 946 186 77 817 763 497 804 227 637 637 616 901 208 313 393 932 910 80 508 865 744 667 557 212 53 312 650 661 756 756 26 437 85 249 573 885...
output:
82 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0...
result:
points 1.0 First Answer Correct, Second Line Correct
Test #9:
score: 5
Accepted
time: 165ms
memory: 4472kb
input:
43178 809 735 401 277 290 702 55 859 346 568 779 257 194 953 93 478 880 951 299 939 28 476 689 331 160 760 14 846 768 174 332 497 166 669 240 128 369 27 843 462 575 501 696 740 865 193 759 48 486 920 753 88 706 358 125 104 688 604 307 560 590 649 463 618 736 580 447 594 224 940 824 71 180 203 991 9 ...
output:
78 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0...
result:
points 1.0 First Answer Correct, Second Line Correct
Test #10:
score: 5
Accepted
time: 99ms
memory: 3416kb
input:
27301 304 885 912 38 506 688 688 219 842 448 678 580 910 143 245 417 502 424 737 425 23 619 241 676 103 980 4 682 58 882 666 106 669 863 431 277 241 932 476 188 811 519 359 238 129 535 244 559 767 615 564 374 586 33 460 358 301 189 105 424 763 466 539 966 844 828 887 322 635 871 234 544 743 243 146 ...
output:
65 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0...
result:
points 1.0 First Answer Correct, Second Line Correct
Test #11:
score: 5
Accepted
time: 83ms
memory: 3376kb
input:
31938 269 159 80 159 500 159 534 159 241 159 22 159 368 159 682 159 83 159 847 159 785 159 237 159 118 159 342 159 420 159 659 159 623 159 91 159 79 159 93 159 170 159 337 159 137 159 10 159 972 159 6 159 40 159 89 159 183 159 998 159 160 159 128 159 601 159 792 159 891 159 48 159 461 159 304 159 59...
output:
391 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.66667 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 ...
result:
points 1.0 First Answer Correct, Second Line Correct
Test #12:
score: 5
Accepted
time: 95ms
memory: 3500kb
input:
33877 66 203 17 203 610 203 476 203 942 203 441 203 58 203 595 203 14 203 165 203 337 203 772 203 612 203 385 203 280 203 636 203 874 203 359 203 62 203 994 203 395 203 186 203 766 203 232 203 552 203 599 203 732 203 966 203 580 203 463 203 859 203 702 203 785 203 606 203 378 203 681 203 416 203 599...
output:
389 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 ...
result:
points 1.0 First Answer Correct, Second Line Correct
Test #13:
score: 5
Accepted
time: 119ms
memory: 3732kb
input:
38756 316711304 984776997 294851143 984776997 183805078 984776997 695479205 984776997 4213387 984776997 42631934 984776997 9512700 984776997 230860038 984776997 22529762 984776997 283920215 984776997 460814138 984776997 551939564 984776997 585241093 984776997 15203606 984776997 541984568 984776997 1...
output:
385 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 ...
result:
points 1.0 First Answer Correct, Second Line Correct
Test #14:
score: 5
Accepted
time: 160ms
memory: 4212kb
input:
47469 726902344 699648473 403993419 699648473 439835363 699648473 68293233 699648473 46909729 699648473 273397177 699648473 865012690 699648473 996294387 699648473 327512157 699648473 219542396 699648473 523762710 699648473 876073630 699648473 902886415 699648473 204871097 699648473 24067330 6996484...
output:
432 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 1.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.33333 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.66667 0.00000 0.00000 ...
result:
points 1.0 First Answer Correct, Second Line Correct
Test #15:
score: 5
Accepted
time: 90ms
memory: 3268kb
input:
25091 359090711 34469103 636098931 35731791 568968706 921501782 177426456 742536918 802829441 124170211 850728322 457983024 881042707 854381827 560566863 255097601 22363034 903335398 337545596 546811339 8222695 266960578 952438078 480570557 222073046 50049463 660372653 317199718 839003891 991673962 ...
output:
65 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0...
result:
points 1.0 First Answer Correct, Second Line Correct
Test #16:
score: 5
Accepted
time: 160ms
memory: 4160kb
input:
38521 134847702 735532215 342720086 522555513 456255633 613208254 103492014 236004358 317966718 107573479 518131792 60339691 894484939 803772585 794544127 68734722 196608663 403467448 795978212 635228132 121039956 592951271 449806262 168269555 823465499 603844407 845953872 760103440 832041731 402612...
output:
73 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0...
result:
points 1.0 First Answer Correct, Second Line Correct
Test #17:
score: 5
Accepted
time: 144ms
memory: 3956kb
input:
35949 875507632 348186471 906490282 36351569 850002713 331579198 378846398 206249410 485860853 278208328 936749261 643328819 796911961 943717636 305015264 983647942 348783007 516009592 336542908 939433276 475896350 782557691 467981227 99878402 599772932 831392404 533302374 402699866 896454752 216322...
output:
73 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 1...
result:
points 1.0 First Answer Correct, Second Line Correct
Test #18:
score: 5
Accepted
time: 169ms
memory: 4368kb
input:
42018 31800883 651466005 292339821 264650068 525064248 686808510 302139599 706246265 395180370 304028865 568048274 882263163 268550291 381466015 955977464 142357656 217694070 623826318 72909409 336821882 130444909 922173365 298525604 714600673 268251909 457973627 647319885 171157569 50253648 3403185...
output:
77 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0...
result:
points 1.0 First Answer Correct, Second Line Correct
Test #19:
score: 5
Accepted
time: 130ms
memory: 3736kb
input:
32230 4105360 348572902 852018023 521147871 272858367 237895237 870819109 745323932 71430170 591622946 561689034 8414556 260801692 148825686 99997851 71528739 941720668 331118186 235014368 100014210 18702025 62176522 170937103 532916591 114179390 388407477 314908322 220318045 796045972 335176430 880...
output:
68 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0...
result:
points 1.0 First Answer Correct, Second Line Correct
Test #20:
score: 5
Accepted
time: 172ms
memory: 4324kb
input:
41480 468691550 628926287 75167596 437817252 340638126 554431979 934616978 785581819 8292253 382968644 326123236 684622017 476796430 468401593 248907314 392984693 772998458 669553409 537282346 48742536 998572069 586379742 706546009 58412638 34925004 473960707 885118679 619796951 18555941 56524184 59...
output:
78 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0...
result:
points 1.0 First Answer Correct, Second Line Correct