CT57690

The Violet segments of Pia

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Before the gates of the acacia flats of Thornveld close for winter, Pia must finish the segments ledger - one figure at a time. 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 <= 2722; 0 <= a[i] <= 1000000.

Example 1:

Input: 1068 246009 44974 63625 808630 512880 294652 215950 197528 174649 389770 529236 140711 997612 93161 717012 729685 467032 469205 779237 687757 101461 257046 169719 53727 699399 122328 869834 900315 296183 957316 400308 281316 955229 651020 318547 544815 243053 592314 767994 411630 3619 716440 990552 366599 541997 899523 563489 553219 556862 927502 683314 193854 116500 171395 642959 302879 151722 391128 594729 832812 136121 853000 315236 243196 721626 217504 919821 491846 77529 136895 149627 673823 868026 688140 357335 793509 878744 199483 427614 896094 33332 676596 813420 402409 194939 422432 560250 379056 316888 479606 149360 331556 752113 400916 890570 341614 589509 95780 352871 279181 45112 752152 556537 565109 770097 297737 541111 465722 200597 573435 730258 403603 962020 834816 52159 7…
Output: 528013325

Example 2:

Input: 1809 617 533126 14996 561375 394821 976801 560813 151894 944214 99289 276404 566690 349323 429726 4264 999920 497427 180714 810042 601261 553096 797893 203216 917217 786923 16913 691792 130633 773260 413258 799347 223015 896601 126642 894415 831556 603046 807625 171680 386659 608298 579719 894431 521154 906526 644961 377855 898473 690989 932368 129019 996589 454153 588785 742661 806521 994882 889782 685392 287050 611275 892173 422168 919352 601870 367551 365339 63210 251476 421885 449869 444560 976542 321314 176676 764077 131980 850513 492813 491935 898444 814504 490427 250722 438888 645672 320903 469233 689024 942903 247051 249372 193581 725926 338786 184209 765372 35659 599909 873182 507988 977252 449488 293038 984381 641949 142301 960714 202765 807827 102913 674073 890955 942494 673198 …
Output: 902981327

Example 3:

Input: 2197 844076 863117 641025 81585 748345 973511 61977 441495 551562 916269 669636 567473 554565 492929 212686 540887 929463 989350 684051 767223 728376 194674 998351 879376 870749 406627 625365 626541 65721 988059 618328 659724 738181 889997 14005 132561 267748 783692 935705 664957 329729 451681 659055 585871 537250 632331 837045 407712 728264 695729 797411 621145 336927 410528 35045 932628 112085 851238 626884 75462 497820 125626 635587 528583 561572 873241 788742 874900 234634 255230 993539 940631 976479 967994 138197 396129 263258 504907 793696 816024 157715 447645 790712 87529 161550 272154 627322 374603 488884 657849 461745 818194 761700 540431 477066 393919 889378 295972 987200 865621 445311 213390 462483 646396 448767 171274 639633 241879 722399 941147 126405 772252 733067 57848 60893…
Output: 1088001977

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The Violet segments of Pia - MEDIUM Coding Problem | CodeTikki