CT59090

Farhan Counts the segments

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Legend says the vault under the foggy moor of Greyfen opens only for a perfect tally of segments. Farhan means to find out. 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 <= 1681; 0 <= a[i] <= 1000000.

Example 1:

Input: 691 740683 653651 372277 801534 104521 232678 171772 748885 191302 414514 402190 457081 236552 899867 395841 92480 289937 102895 831975 301231 188502 363255 250066 766657 624449 512928 491060 626122 240679 235370 717889 931024 168238 406931 712454 554654 242937 334177 41595 196204 579911 499079 390938 396067 839456 117491 674939 552299 342310 218488 212205 660550 317005 906223 250425 801359 163184 240932 356558 556607 203705 629529 776990 365222 842548 681416 598674 304260 894 442024 65152 75773 731018 25635 522904 10883 275102 20630 994754 632662 525666 998911 484788 922107 593248 946163 94516 34001 826807 655859 753901 634756 658924 434442 496042 521687 658969 573476 611768 112273 172954 619283 50631 328059 899591 242586 567535 811807 197612 994934 820589 14582 239188 301517 43737 68785 …
Output: 331678095

Example 2:

Input: 311 380020 948120 762949 987980 415080 934867 683003 988631 51870 925149 182475 552551 875892 89003 448666 410733 769967 216154 195297 875896 70886 497630 775316 950602 527888 475113 776535 940925 286394 655896 590908 223467 533760 210878 872406 256342 77066 628761 460105 398104 635496 396434 352137 343662 950415 441593 677114 357681 650692 911609 129180 449874 296289 630583 38117 75091 942621 499799 8745 810394 208617 143013 919573 108638 968038 274450 31777 615009 688833 974073 904202 867246 371738 423250 857799 626793 112072 517827 226701 345413 413304 947366 981080 731488 171337 994909 59750 17961 505297 36283 950111 873908 724666 973155 225579 351092 834997 464838 632261 604637 128718 451065 964533 816886 987000 453798 956299 936863 594430 964150 55244 828149 546506 420521 242252 4985…
Output: 153405422

Example 3:

Input: 1563 964031 334654 256147 840746 431408 835499 736057 771232 163622 89865 865467 481986 785660 112417 581626 145830 743661 212576 461107 874698 481834 476449 991889 448908 182086 103791 679365 613270 346671 138204 82449 26597 737048 945990 906652 45976 309063 940632 584000 760893 487915 24858 901069 81449 481540 669031 117521 876698 58661 792669 893677 166829 121854 52706 379957 660386 65194 577466 598847 953178 852185 795307 899593 678156 136448 456056 702575 487390 450604 411949 714587 662234 970326 265268 144984 66229 705498 727016 305532 526998 347901 690041 840236 833087 787329 323757 869538 986188 351013 334631 921807 225462 277838 94157 722959 267008 965607 703210 361756 251940 993912 158792 720222 99729 394941 544997 194323 546971 988645 68272 110067 934071 466948 912486 932841 398…
Output: 770958061

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.