QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #229500 | #7616. Jump Graph | c20230107 | WA | 10ms | 14856kb | C++14 | 798b | 2023-10-28 16:18:43 | 2023-10-28 16:18:43 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
using namespace std;
int a[333333],st[333333],top=0,p[333333];
int l[333333],r[333333],si[333333],s[333333],ss[33333];
signed main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
p[a[i]]=i;
}
for(int i=1;i<=n;i++){
while(top&&a[i]>a[st[top]]){
r[st[top--]]=i;
}
l[i]=st[top];
st[++top]=i;
}
for(int i=1;i<=top;i++) r[st[i]]=n+1;
for(int x=1,i=p[1];x<=n;i=p[++x]){
s[i-1]++;
ss[i+1]++;
si[i]++;
if(a[l[i]]>a[r[i]]){
si[l[i]]+=si[i];
}else{;
si[r[i]]+=si[i];
}
if(l[i]>1) s[l[i]-1]+=si[i];
if(r[i]<n) ss[r[i]+1]+=si[i];
}
for(int i=n;i>=1;i--){
s[i]+=s[i+1];
}
for(int i=1;i<=n;i++){
ss[i]+=ss[i-1];
cout<<s[i]+ss[i]<<" ";
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 11900kb
input:
6 1 6 3 2 5 4
output:
11 7 7 7 6 8
result:
ok single line: '11 7 7 7 6 8 '
Test #2:
score: 0
Accepted
time: 0ms
memory: 13944kb
input:
2 1 2
output:
1 1
result:
ok single line: '1 1 '
Test #3:
score: 0
Accepted
time: 1ms
memory: 11780kb
input:
36 9 29 1 3 14 31 24 21 10 18 22 16 8 7 15 12 17 19 25 28 27 34 11 6 32 4 20 13 2 35 23 26 33 36 30 5
output:
92 89 90 90 91 78 73 71 71 71 65 65 64 64 63 65 65 70 74 85 95 91 111 111 109 111 110 110 110 107 136 136 137 136 168 168
result:
ok single line: '92 89 90 90 91 78 73 71 71 71 ...10 107 136 136 137 136 168 168 '
Test #4:
score: 0
Accepted
time: 1ms
memory: 11764kb
input:
63 30 17 34 8 29 57 2 62 35 27 24 22 54 53 60 37 31 19 1 5 20 14 3 36 38 40 56 39 50 32 51 9 15 52 55 45 63 41 6 47 23 7 33 10 26 61 16 58 43 42 44 48 28 12 49 11 59 4 21 25 46 13 18
output:
204 204 202 204 204 204 209 191 197 196 195 195 194 198 179 176 172 170 170 170 170 172 172 172 179 188 186 187 186 187 185 187 187 188 191 193 167 202 202 198 199 199 197 199 199 183 190 183 183 183 183 184 185 185 184 187 181 190 190 191 190 191 191
result:
ok single line: '204 204 202 204 204 204 209 19...87 181 190 190 191 190 191 191 '
Test #5:
score: 0
Accepted
time: 1ms
memory: 11896kb
input:
110 70 59 102 66 81 43 31 26 52 23 88 49 9 7 76 108 25 101 89 73 4 22 77 94 64 24 16 58 47 30 28 45 68 15 84 36 21 78 56 46 32 62 65 55 61 20 74 2 83 33 105 110 50 60 85 42 96 98 6 10 41 51 97 8 72 86 69 93 82 67 100 57 75 1 106 11 40 35 17 39 18 14 34 53 92 12 54 3 95 103 99 80 5 27 37 29 63 13 90 ...
output:
386 386 377 379 375 375 374 374 373 376 372 377 376 376 376 344 359 344 341 339 339 339 340 323 325 324 324 322 321 320 320 320 321 329 315 322 322 313 314 313 313 313 314 317 316 317 316 320 319 331 331 306 357 357 357 358 358 352 354 354 355 356 352 353 353 353 354 353 354 354 352 365 364 365 350 ...
result:
ok single line: '386 386 377 379 375 375 374 37...87 387 386 386 385 389 388 407 '
Test #6:
score: 0
Accepted
time: 0ms
memory: 13860kb
input:
192 186 25 95 115 187 44 154 54 80 121 89 117 68 74 27 137 171 112 22 60 6 109 97 14 101 166 82 126 15 69 92 51 174 162 65 156 132 150 56 138 20 93 85 103 164 26 77 124 170 34 185 188 116 98 120 123 148 16 100 49 53 88 179 102 94 169 96 37 140 48 146 40 125 141 45 129 11 19 175 43 144 184 5 10 7 2 8...
output:
693 693 693 694 649 653 644 645 645 643 644 642 643 642 643 643 639 644 644 643 644 641 642 642 642 640 648 645 646 646 646 647 631 649 649 646 647 643 644 640 641 640 641 641 640 651 651 652 652 665 665 658 708 708 708 710 708 709 706 707 707 708 692 697 697 690 691 691 690 692 688 691 691 689 690 ...
result:
ok single line: '693 693 693 694 649 653 644 64...34 840 839 838 836 836 836 837 '
Test #7:
score: 0
Accepted
time: 1ms
memory: 11820kb
input:
336 3 269 28 151 303 89 230 218 88 70 150 254 173 87 75 247 293 310 32 250 45 276 233 257 315 126 128 104 181 14 11 152 268 258 334 299 109 122 278 226 251 277 98 21 36 67 39 163 259 188 241 326 170 147 153 48 201 246 238 145 162 49 91 192 13 191 59 236 165 167 202 34 210 312 220 194 234 330 282 183...
output:
1475 1473 1474 1474 1463 1467 1465 1463 1462 1462 1462 1460 1464 1463 1463 1463 1466 1470 1487 1486 1487 1485 1487 1487 1480 1504 1503 1504 1501 1502 1502 1502 1503 1508 1367 1396 1396 1396 1388 1389 1389 1382 1380 1380 1380 1380 1381 1381 1384 1387 1387 1365 1379 1379 1378 1379 1379 1376 1367 1367 ...
result:
ok single line: '1475 1473 1474 1474 1463 1467 ... 1426 1449 1449 1448 1486 1486 '
Test #8:
score: 0
Accepted
time: 1ms
memory: 11828kb
input:
588 114 95 54 22 424 384 47 439 9 60 331 317 361 454 86 123 79 417 96 240 208 310 26 113 339 498 291 141 425 169 492 177 191 567 260 279 514 63 27 421 229 482 36 183 326 118 35 426 456 367 55 245 222 287 362 167 533 84 46 313 365 571 464 221 281 503 180 163 522 289 404 548 110 350 159 147 57 323 211...
output:
2271 2270 2269 2269 2268 2271 2271 2266 2273 2273 2273 2274 2274 2267 2280 2279 2280 2273 2275 2274 2275 2273 2275 2275 2276 2274 2298 2298 2297 2299 2297 2300 2300 2275 2308 2308 2298 2298 2298 2297 2299 2292 2295 2295 2295 2295 2295 2295 2293 2291 2291 2290 2291 2291 2292 2294 2290 2309 2309 2309 ...
result:
ok single line: '2271 2270 2269 2269 2268 2271 ... 3252 3252 3252 3250 3252 3252 '
Test #9:
score: 0
Accepted
time: 1ms
memory: 11924kb
input:
1029 97 622 1025 939 297 294 590 710 36 75 492 654 729 722 933 672 194 471 647 456 917 561 356 683 1027 650 873 723 911 986 508 680 384 390 530 179 823 512 884 130 266 343 715 517 524 398 905 855 670 6 354 952 581 16 302 958 60 52 519 810 927 712 258 96 336 185 363 120 999 779 587 61 478 286 614 845...
output:
5001 5001 4992 4980 4979 4979 4979 4977 4979 4979 4980 4981 4981 4986 4979 4979 4979 4979 4979 4980 4977 4981 4981 4981 4835 4859 4858 4859 4859 4831 4833 4830 4831 4831 4831 4832 4831 4836 4831 4835 4835 4836 4835 4836 4835 4836 4835 4842 4840 4840 4840 4839 4846 4846 4846 4842 4849 4849 4849 4851 ...
result:
ok single line: '5001 5001 4992 4980 4979 4979 ... 5271 5271 5270 5270 5270 5270 '
Test #10:
score: 0
Accepted
time: 2ms
memory: 11840kb
input:
1800 766 1174 1086 920 844 1508 1276 441 919 16 1053 1661 1742 1363 1 773 755 1636 84 521 1595 86 1506 724 1375 698 271 800 1696 472 15 1458 542 1662 1343 53 168 917 931 1660 257 19 1084 1684 1597 617 1553 270 1691 1443 1540 410 952 594 963 664 1657 1232 1429 253 1473 905 304 678 515 993 1357 998 18...
output:
9797 9796 9796 9795 9795 9792 9793 9793 9792 9793 9793 9795 9723 9733 9733 9732 9733 9729 9733 9733 9731 9732 9729 9730 9727 9727 9727 9727 9705 9717 9717 9716 9718 9711 9710 9710 9710 9711 9712 9710 9714 9714 9714 9714 9723 9723 9722 9723 9713 9723 9719 9720 9719 9720 9719 9721 9707 9713 9712 9713 ...
result:
ok single line: '9797 9796 9796 9795 9795 9792 ... 9476 9480 9477 9480 9479 9479 '
Test #11:
score: 0
Accepted
time: 0ms
memory: 11836kb
input:
3150 2016 1004 1533 2983 2188 426 737 2057 889 194 2681 613 2955 2104 333 689 2999 1485 1701 1761 29 2888 2328 2642 1585 2730 971 2355 1359 1350 2083 2347 434 2534 1629 2931 1776 969 1323 136 1721 1627 1425 277 3068 1390 614 2370 834 1407 2849 1751 928 292 1637 231 1636 2809 2433 462 1509 191 848 30...
output:
16472 16472 16472 16464 16464 16464 16464 16464 16464 16464 16463 16469 16467 16470 16470 16470 16452 16468 16468 16468 16469 16460 16462 16461 16462 16454 16456 16452 16452 16452 16452 16453 16455 16454 16460 16457 16468 16468 16467 16468 16467 16468 16467 16467 16459 16502 16502 16500 16502 16502 ...
result:
ok single line: '16472 16472 16472 16464 16464 ... 18151 18151 18152 18152 18185 '
Test #12:
score: 0
Accepted
time: 0ms
memory: 11932kb
input:
5512 5122 249 4482 37 1130 342 4012 2911 3534 5000 4910 5329 1780 4651 2673 2255 2130 66 1916 1854 3186 633 4080 2088 4802 3713 3806 2500 2800 4847 1789 5071 3476 2972 2785 3228 95 3989 178 4714 3450 4936 5212 2442 5276 1168 2688 2515 3009 4173 3218 3292 2090 2854 129 391 4120 609 4027 2703 680 1141...
output:
34679 34679 34674 34675 34674 34675 34673 34675 34675 34675 34682 34626 34637 34628 34628 34626 34624 34624 34623 34624 34623 34629 34628 34635 34632 34643 34641 34642 34642 34642 34650 34640 34642 34641 34641 34640 34642 34641 34646 34645 34650 34650 34652 34664 34634 34638 34637 34638 34638 34632 ...
result:
ok single line: '34679 34679 34674 34675 34674 ... 34878 34894 34893 34894 34894 '
Test #13:
score: 0
Accepted
time: 1ms
memory: 11888kb
input:
2 2 1
output:
1 1
result:
ok single line: '1 1 '
Test #14:
score: 0
Accepted
time: 0ms
memory: 14164kb
input:
9646 4083 1911 8250 7773 2595 5073 8165 8693 4036 236 4365 2065 7669 2442 3631 5796 5741 9047 1922 5503 7747 2031 4187 7895 3089 9381 3282 5635 7378 8720 7254 1678 3462 786 4569 7287 3388 5315 4446 9006 3062 3630 1182 7230 8481 7938 8114 1581 3290 4126 5330 2311 7929 227 1457 9607 7240 23 7008 8837 ...
output:
56216 56216 56212 56212 56212 56212 56213 56209 56215 56215 56214 56216 56213 56216 56216 56216 56217 56211 56228 56228 56227 56228 56228 56228 56231 56213 56238 56238 56239 56233 56230 56230 56229 56230 56230 56230 56235 56234 56235 56229 56239 56238 56239 56239 56235 56237 56230 56231 56231 56232 ...
result:
ok single line: '56216 56216 56212 56212 56212 ... 76814 76840 76840 76839 76841 '
Test #15:
score: 0
Accepted
time: 5ms
memory: 12136kb
input:
16880 2620 5517 15317 14624 3162 3872 16556 1032 12526 8373 5617 9938 2396 9520 5386 10125 14441 8334 3564 1734 14365 9674 4994 1584 8939 3039 9744 11195 1039 10794 14520 5616 7740 14885 2305 5122 2334 144 7635 14842 16058 225 8844 11893 10115 12681 7593 15281 10705 1275 11916 5855 10548 16245 3159 ...
output:
126395 126395 126394 126394 126394 126394 126346 126352 126345 126345 126345 126343 126345 126344 126345 126345 126340 126347 126346 126346 126338 126338 126337 126337 126336 126338 126338 126341 126345 126345 126344 126361 126361 126356 126371 126370 126370 126370 126370 126373 126368 126376 126376...
result:
ok single line: '126395 126395 126394 126394 12...78 109082 109095 109094 109095 '
Test #16:
score: 0
Accepted
time: 8ms
memory: 14536kb
input:
29540 21660 2028 12964 6138 24030 20445 10053 17204 20432 863 17996 13607 10819 11136 15689 9902 14559 17935 13982 16518 26375 3516 18377 15190 11520 18426 14397 21421 27432 13490 24097 2332 5574 1451 24688 28254 18558 25985 26192 29067 10134 15556 10078 11734 29033 18604 19513 12836 5044 24817 2381...
output:
225212 225212 225211 225212 225209 225209 225209 225209 225203 225204 225196 225195 225195 225195 225194 225197 225197 225196 225200 225200 225194 225214 225213 225213 225213 225212 225215 225215 225213 225241 225239 225240 225239 225240 225240 225241 225276 225276 225277 225271 225310 225308 225309...
result:
ok single line: '225212 225212 225211 225212 22...47 221047 221048 221048 221050 '
Test #17:
score: -100
Wrong Answer
time: 10ms
memory: 14856kb
input:
51695 25757 46390 46936 35417 38407 50322 34131 45113 48067 40556 43162 38421 18517 22542 34293 39180 16755 38132 44939 5760 21027 4643 41258 22179 40253 14694 6659 18296 47470 19801 7302 45675 31360 9788 33220 33106 26159 28585 35811 13400 37315 18401 23221 22583 7530 47246 38366 49277 25080 50788 ...
output:
611093 611088 611086 611087 611086 611042 611046 611037 611007 611007 611000 610995 610994 610990 610990 610981 610942 610941 610935 610942 610939 610902 610898 610898 610894 610893 610892 610882 610866 610877 610876 610865 610863 610862 610854 610849 610848 610845 610844 610848 610845 610848 610846...
result:
wrong answer 1st lines differ - expected: '391066 391066 391065 391067 39...084 498084 498083 498085 498085', found: '611093 611088 611086 611087 61...56935100 8257160395 8257385686 '