QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #329092 | #4802. Ternary Search | maojun | TL | 9ms | 5480kb | C++20 | 577b | 2024-02-16 13:06:17 | 2024-02-16 13:06:18 |
Judging History
answer
#include<bits/extc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
int n,a[N];
ll ans[N];
inline void calc(){
for(int p=1;p<=n;p++){
ll sum=0;
for(int i=1;i<=p;i++){
int L=0,R=0;
for(int j=1;j<i;j++)if(a[j]>a[i])L++;
for(int j=p;j>i;j--)if(a[j]>a[i])R++;
sum+=min(L,R);
}
ans[p]=min(ans[p],sum);
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
memset(ans,0x3f,sizeof ans);
calc();for(int i=1;i<=n;i++)a[i]=-a[i];calc();
for(int i=1;i<=n;i++)printf("%lld\n",ans[i]);
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 5412kb
input:
9 11 4 5 14 1 9 19 8 10
output:
0 0 0 0 2 3 3 6 7
result:
ok 9 numbers
Test #2:
score: 0
Accepted
time: 1ms
memory: 5348kb
input:
1 167959139
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: 0
Accepted
time: 1ms
memory: 5404kb
input:
10 802030518 983359971 96204862 640274071 796619138 71550121 799843967 598196518 402690754 446173607
output:
0 0 0 1 1 3 3 5 7 9
result:
ok 10 numbers
Test #4:
score: 0
Accepted
time: 0ms
memory: 5416kb
input:
200 280383943 994080326 443906342 107926501 414713819 45732490 370693588 928126378 581740643 189811400 142817640 218386999 447997927 640003704 637428425 151698689 209462128 155599305 390080477 958251194 515653943 751042490 1186761 443171900 968975479 829084542 462837689 157692260 607049612 606116398...
output:
0 0 0 0 1 1 3 4 5 8 12 15 17 18 19 25 30 35 38 38 41 42 54 60 60 62 69 81 87 93 109 112 124 126 139 148 152 164 169 180 187 193 211 221 226 244 244 252 264 273 286 307 316 328 339 358 378 392 408 416 439 445 447 463 490 503 521 536 547 567 594 619 638 638 659 668 702 724 729 758 772 777 816 836 845 ...
result:
ok 200 numbers
Test #5:
score: 0
Accepted
time: 0ms
memory: 5420kb
input:
205 798721503 163087712 141733092 316449050 127486543 148708227 646902722 254007921 648511970 807308399 362190286 356609247 109012359 421274742 647319513 34648738 573893368 682755343 757300027 674077117 324958818 106483343 305773689 837270774 883136402 847234810 756696363 354615040 58759846 32739626...
output:
0 0 0 0 1 2 2 3 3 3 6 10 16 19 22 23 28 34 35 37 45 49 52 61 64 65 69 80 86 86 90 95 105 109 112 113 120 133 136 136 152 166 180 181 196 214 231 245 266 287 297 309 330 341 358 368 383 387 393 414 434 448 456 484 494 506 521 534 543 551 561 596 621 626 634 644 655 692 732 743 750 767 807 846 869 876...
result:
ok 205 numbers
Test #6:
score: 0
Accepted
time: 5ms
memory: 5480kb
input:
300 310486422 145995805 744831366 913444383 54589620 760840937 351438066 497043991 437781614 854981783 137693561 940050335 22692948 779922082 713507093 773173557 700078081 889701510 709956997 620732070 535136113 428608043 656183847 627784826 348865620 634573459 271461607 622653937 662713549 35111166...
output:
0 0 0 0 1 2 3 5 7 9 11 14 15 19 22 25 27 33 36 38 40 41 45 49 50 55 55 60 69 71 76 80 99 110 110 116 117 125 148 151 175 182 208 223 229 245 256 259 280 285 302 314 332 337 345 369 380 398 403 405 413 447 468 484 494 511 537 550 555 585 601 616 637 659 664 695 715 730 755 757 762 777 787 805 842 860...
result:
ok 300 numbers
Test #7:
score: 0
Accepted
time: 9ms
memory: 5428kb
input:
400 418345904 425283570 502048611 949470422 1539681 816939105 835973188 548395262 912622971 892988664 137695077 200974194 416058059 46966392 717454596 508236934 577018523 271703565 404875844 116208843 795979997 232130698 201391686 396794371 873677110 643916648 979303165 209135495 365323814 220296329...
output:
0 0 0 0 0 1 3 4 7 8 8 9 11 11 16 20 25 28 32 33 43 47 50 55 67 73 73 83 90 98 99 103 110 116 124 135 142 160 175 182 195 197 210 216 217 222 228 234 254 268 295 306 334 337 349 357 383 388 392 420 441 460 473 474 480 491 506 532 548 549 572 589 629 635 674 700 711 714 744 773 797 809 815 852 860 895...
result:
ok 400 numbers
Test #8:
score: -100
Time Limit Exceeded
input:
10000 654266585 918195389 61806003 512260326 35440115 595032690 353979552 32592347 712550231 380796590 139710715 828841723 115308806 675515525 910499939 780014628 924148821 719010926 731425929 381219228 963983190 359044179 76245693 524823828 890447664 856974623 751508756 830808517 963022804 54360656...