CT57710

Ulrica's Ledger of segments

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

At the forest village of Briarthorn, Ulrica records each segments in a worn leather ledger. The guild wants answers, not guesses. Task: Heights a[i] form a skyline; after rain, water rests between higher bars. Print the total trapped water. Input format: First line: n. Second line: n nonnegative integers. Output format: Print the trapped water volume (fits 64-bit). Constraints: 1 <= n <= 1386; 0 <= a[i] <= 1000000.

Example 1:

Input: 855 759331 567868 902180 613392 358131 810416 420408 61358 93717 13495 123108 153420 308913 736122 828443 931103 541988 647460 549606 177792 253452 70553 700780 460446 425105 98128 351456 855768 915130 172199 940058 699402 359663 9206 320070 321713 649468 649081 129696 823105 714603 402503 772673 348822 975964 625759 535371 264288 546855 591649 292769 461174 295136 854479 129044 876356 650650 771254 836928 231369 312993 478472 706370 383313 484005 972159 956129 608628 995695 650625 255955 462900 966245 763412 472940 362411 430522 37296 225111 965797 220938 495561 824133 431115 670388 935768 979105 873703 521675 503478 818339 283188 791809 369000 773344 633423 795576 239454 524215 996016 766316 641911 947863 379007 909432 570128 30374 604548 629127 675578 316400 389126 322519 692732 321675 …
Output: 404102584

Example 2:

Input: 555 97558 624334 198185 83086 622975 112885 422336 432090 195052 394770 887669 282126 516290 292262 805270 840520 547802 478247 324903 489712 158268 773204 113798 567045 62070 712310 616803 474420 731261 72173 431150 4 38494 532385 358114 565770 345700 841159 211971 496594 37161 782955 501546 421230 722052 327635 283192 147067 490012 633108 427604 855825 167372 821071 248324 890384 123202 608225 502854 753581 640250 456229 458918 336450 12896 988974 375997 916161 99469 755631 775884 220896 409512 249860 64015 320975 124615 184800 794827 394006 993264 607619 112833 844197 113511 625926 456123 64469 55372 379358 921393 817117 107730 332545 583689 708745 749434 728550 930506 293021 776221 316638 793066 276860 889596 82997 514381 802910 807977 951487 226127 60188 386444 514980 597519 162200 12…
Output: 267683223

Example 3:

Input: 1303 958091 896194 955369 280638 11303 550754 467219 759697 929068 127329 662882 410129 472131 956124 403866 674639 372474 771366 826092 681508 898849 174823 266012 568881 316721 73744 826757 418767 368894 835341 682356 936601 606738 890220 379007 206751 242874 945582 136549 550785 819842 777429 451949 213865 634623 27926 477012 289398 55489 8392 283980 524749 837964 282682 459195 310860 964168 527174 283784 705446 146281 697250 691366 15775 352203 171342 430065 773451 142442 456977 448040 586104 401704 52043 547598 343909 596341 493160 83709 921870 405424 227915 834463 740622 82364 370539 927428 814488 696873 285261 875960 140298 92737 136754 689924 670949 878073 904669 349153 4520 219854 258173 117244 862089 511667 445516 664406 157472 862139 555069 569992 348940 13557 226420 278966 9978…
Output: 634805483

Constraints:

1 <= n <= 1386; 0 <= a[i] <= 1000000.

Loading...
Test Cases:No test cases
No test cases available.
Ulrica's Ledger of segments - MEDIUM Coding Problem | CodeTikki