QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#89950#4151. 拦截导弹Alex10086100 ✓193ms4772kbC++142.8kb2023-03-21 20:40:182023-03-21 20:40:22

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-21 20:40:22]
  • 评测
  • 测评结果:100
  • 用时:193ms
  • 内存:4772kb
  • [2023-03-21 20:40:18]
  • 提交

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