CT52278

Kian and the Twilight segments

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Every season at the mountain city of Highreach, someone must tally the donation drive. This year the task falls to Kian, armed only with the segments register. 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 <= 1477; 0 <= a[i] <= 1000000.

Example 1:

Input: 1217 28153 1963 334637 739365 236202 716500 168004 693122 842168 744118 824462 8698 976829 697718 733171 732443 536014 539822 398822 863895 280970 56925 633957 68724 874213 872708 308021 542403 874653 93822 221581 896292 898692 610878 888363 232414 257895 644477 492043 267349 197332 528025 803239 854678 565425 844465 338457 5706 792909 769265 35649 251133 865161 231123 998962 19772 128867 816876 91637 340839 198264 622196 553512 882800 742472 656256 718611 711633 325909 810468 606521 286531 424846 467501 45104 895556 539723 329553 657101 479676 587502 136309 275549 691961 452400 787433 659293 377128 407056 653869 468763 761484 255899 176230 73150 91037 425292 464736 730631 318757 705225 649219 652905 849626 588598 701623 538212 355798 695443 807377 505131 681997 256770 970371 195373 667183…
Output: 591609876

Example 2:

Input: 566 904567 575276 973973 254260 852658 14741 814702 646986 313945 31426 722424 421663 807275 858009 285809 81644 235323 352267 814377 85346 571873 421736 91667 467907 234581 607009 788543 130214 848129 309196 71228 87907 560009 441648 254635 163208 421248 811755 515765 731192 961640 240742 206865 854268 63104 827330 640302 281773 807913 538671 890864 137698 353483 584033 372171 205337 12932 216148 71931 678767 348794 730423 315531 625358 871050 529916 1437 481951 768069 85814 626617 357859 742477 752251 134703 908102 639143 309100 140585 166890 667639 444301 797760 67374 840190 462975 559256 772994 803181 288498 772775 246309 314989 898340 650331 756066 650334 260322 458138 616520 459816 528561 11879 708553 839546 649833 519816 794151 73244 408941 435598 796385 589508 540597 588887 934583 …
Output: 290032173

Example 3:

Input: 513 135928 433706 823606 439793 176896 198840 474071 298380 148558 315624 597504 317352 49508 364775 565988 742186 829775 979670 629563 666699 449759 809878 15458 957160 901744 701163 8165 430303 32885 815393 160293 347315 359124 966533 818906 161201 810295 730917 515965 463563 821940 536292 759471 698928 220151 805540 478475 413646 942323 709943 249714 18165 774000 396181 978870 885775 220080 826785 310303 923225 399187 950598 903622 327976 128233 753472 40087 516394 300793 766259 837371 467826 352628 541265 713624 993047 119101 633669 749751 132483 617874 512551 468878 868075 158892 618947 98704 555526 775101 46357 531635 954180 143696 232311 91312 847005 46697 342806 268631 965864 658118 288213 453903 120508 441071 696466 971026 890362 175722 181414 721086 528092 284267 248913 547175 70…
Output: 237653695

Constraints:

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

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