fork download
copy 
  1.  
  2.  
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5.  
  6. #define file "o"
  7. #define ff(i, a, b) for(auto i=(a); i<=(b); ++i)
  8. #define ffr(i, b, a) for(auto i=(b); i>=(a); --i)
  9. #define nl "\n"
  10. #define ss " "
  11. #define pb emplace_back
  12. #define fi first
  13. #define se second
  14. #define sz(s) (int)s.size()
  15. #define all(s) (s).begin(), (s).end()
  16. #define ms(a,x) memset(a, x, sizeof (a))
  17. #define cn continue
  18. #define re exit(0)
  19.  
  20. typedef long long ll;
  21. typedef unsigned long long ull;
  22. typedef long double ld;
  23. typedef vector<int> vi;
  24. typedef vector<ll> vll;
  25. typedef pair<int, int> pii;
  26. typedef pair<ll, ll> pll;
  27. typedef vector<pii> vpii;
  28. typedef vector<pll> vpll;
  29.  
  30. mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  31. ll ran(ll l, ll r)
  32. {
  33.     return uniform_int_distribution<ll> (l, r)(rng);
  34. }
  35.  
  36. inline void rf()
  37. {
  38.     ios_base::sync_with_stdio(false);
  39.     cin.tie(nullptr); cout.tie(nullptr);
  40.     if(fopen(file".inp","r"))
  41.     {
  42.         freopen(file".inp","r",stdin);
  43.         freopen(file".out","w",stdout);
  44.     }
  45. }
  46.  
  47. const int mod=998244353;
  48. const int maxn=3e5+15;
  49. const ll inf=1e18;
  50. const int INF = 2e9;
  51. const int MINF = -2e9;
  52.  
  53. template<typename T> inline void add(T &x, const T &y)
  54. {
  55.     x+=y;
  56.     if(x>=mod) x-=mod;
  57.     if(x<0) x+=mod;
  58. }
  59.  
  60. template<typename T> inline bool maxi(T &a, T b)
  61. {
  62.     if(a>=b) return 0;
  63.     a=b; return 1;
  64. }
  65.  
  66. template<typename T> inline bool mini(T &a, T b)
  67. {
  68.     if(a<=b) return 0;
  69.     a=b; return 1;
  70. }
  71.  
  72. int n;
  73. vi A, P, M, Q, K, BL, BR, tree_seg;
  74.  
  75. void build(int node, int l, int r) 
  76. {
  77.     if (l == r) 
  78.     {
  79.         tree_seg[node] = BR[l];
  80.         return;
  81.     }
  82.     int mid = l + (r - l) / 2;
  83.     build(2 * node, l, mid);
  84.     build(2 * node + 1, mid + 1, r);
  85.     tree_seg[node] = min(tree_seg[2 * node], tree_seg[2 * node + 1]);
  86. }
  87.  
  88. int query(int node, int l, int r, int ql, int qr, int x)
  89. {
  90.     if (l > qr || r < ql || tree_seg[node] >= x) return -1;
  91.     if (l == r) return l;
  92.     int mid = l + (r - l) / 2;
  93.     int res = query(2 * node, l, mid, ql, qr, x);
  94.     if (res != -1) return res;
  95.     return query(2 * node + 1, mid + 1, r, ql, qr, x);
  96. }
  97.  
  98. inline int getMaxY_Q(int val, int lenR) 
  99. {
  100.     int low = 0, high = lenR, ans = 0;
  101.     while (low <= high) 
  102.     {
  103.         int mid = low + (high - low) / 2;
  104.         if (Q[mid] > val) { ans = mid; low = mid + 1; } 
  105.         else high = mid - 1;
  106.     }
  107.     return ans;
  108. }
  109.  
  110. inline int getMaxY_K(int val, int lenR) 
  111. {
  112.     int low = 0, high = lenR, ans = 0;
  113.     while (low <= high) 
  114.     {
  115.         int mid = low + (high - low) / 2;
  116.         if (K[mid] < val) { ans = mid; low = mid + 1; } 
  117.         else high = mid - 1;
  118.     }
  119.     return ans;
  120. }
  121.  
  122. inline int getMaxX_P(int val, int lenL) 
  123. {
  124.     int low = 0, high = lenL, ans = 0;
  125.     while (low <= high) 
  126.     {
  127.         int mid = low + (high - low) / 2;
  128.         if (P[mid] > val) { ans = mid; low = mid + 1; } 
  129.         else high = mid - 1;
  130.     }
  131.     return ans;
  132. }
  133.  
  134. inline int getMaxX_M(int val, int lenL)
  135. {
  136.     int low = 0, high = lenL, ans = 0;
  137.     while (low <= high)
  138.     {
  139.         int mid = low + (high - low) / 2;
  140.         if (M[mid] < val) { ans = mid; low = mid + 1; } 
  141.         else high = mid - 1;
  142.     }
  143.     return ans;
  144. }
  145.  
  146. void solve() 
  147. {
  148.     cin >> n;
  149.     A.assign(n + 1, 0);
  150.     ff(i, 1, n) cin >> A[i];
  151.  
  152.     int lenL = 0;
  153.     P.assign(n + 1, 0); M.assign(n + 1, 0);
  154.     P[0] = INF; M[0] = MINF;
  155.     ff(i, 1, n)
  156.     {
  157.         if (i == 1) { lenL = 1; P[1] = A[1]; M[1] = A[1]; } 
  158.         else 
  159.         {
  160.             if (A[i] < P[i - 1]) { lenL = i; P[i] = A[i]; M[i] = M[i - 1]; } 
  161.             else if (A[i] > M[i - 1]) { lenL = i; P[i] = P[i - 1]; M[i] = A[i]; } 
  162.             else break;
  163.         }
  164.     }
  165.  
  166.     int lenR = 0;
  167.     Q.assign(n + 1, 0); K.assign(n + 1, 0);
  168.     Q[0] = INF; K[0] = MINF;
  169.     ff(j, 1, n) 
  170.     {
  171.         int idx = n - j + 1;
  172.         if (j == 1) { lenR = 1; Q[1] = A[idx]; K[1] = A[idx]; } 
  173.         else 
  174.         {
  175.             if (A[idx] < Q[j - 1]) { lenR = j; Q[j] = A[idx]; K[j] = K[j - 1]; } 
  176.             else if (A[idx] > K[j - 1]) { lenR = j; Q[j] = Q[j - 1]; K[j] = A[idx]; } 
  177.             else break;
  178.         }
  179.     }
  180.  
  181.     BL.assign(lenL + 1, 0);
  182.     ff(x, 1, lenL) 
  183.     {
  184.         if (x == 1) BL[x] = max(getMaxY_Q(A[1], lenR), getMaxY_K(A[1], lenR));
  185.         else 
  186.         {
  187.             if (A[x] < P[x - 1]) BL[x] = getMaxY_Q(A[x], lenR);
  188.             else BL[x] = getMaxY_K(A[x], lenR);
  189.         }
  190.     }
  191.  
  192.     BR.assign(lenR + 1, 0);
  193.     ff(y, 1, lenR) 
  194.     {
  195.         int idx = n - y + 1;
  196.         if (y == 1) BR[y] = max(getMaxX_P(A[n], lenL), getMaxX_M(A[n], lenL));
  197.         else 
  198.         {
  199.             if (A[idx] < Q[y - 1]) BR[y] = getMaxX_P(A[idx], lenL);
  200.             else BR[y] = getMaxX_M(A[idx], lenL);
  201.         }
  202.     }
  203.  
  204.     tree_seg.assign(4 * lenR + 5, 0);
  205.     if (lenR > 0) build(1, 1, lenR);
  206.  
  207.     vi dp(lenL + 1, -1);
  208.     dp[0] = lenR;
  209.     int ans = dp[0];
  210.  
  211.     ff(x, 1, lenL) 
  212.     {
  213.         int y_curr = min({dp[x - 1], BL[x], n - x});
  214.         if (y_curr < 0) 
  215.         {
  216.             dp[x] = -1;
  217.             cn;
  218.         }
  219.         int limit = min(lenR, n - x);
  220.         if (y_curr < limit) 
  221.         {
  222.             int k = query(1, 1, lenR, y_curr + 1, limit, x);
  223.             if (k != -1) y_curr = k - 1;
  224.             else y_curr = limit;
  225.         }
  226.         dp[x] = y_curr;
  227.         maxi(ans, x + dp[x]);
  228.     }
  229.     cout << ans << nl;
  230. }
  231.  
  232. signed main()
  233. {
  234.     rf();
  235.     int t; cin>>t;
  236.     while (t--) solve();
  237.     re;
  238. }
Success #stdin #stdout 0.01s 5304KB
comments (?)
stdin
copy 
5
313
665 311 457 865 699 25 986 882 316 953 911 529 261 765 419 689 213 390 539 210 752 122 251 16 253 512 989 156 949 210 548 863 519 93 639 74 877 753 337 678 821 537 161 991 22 893 452 223 714 870 648 984 292 567 47 157 596 778 320 559 411 304 371 39 572 931 374 814 997 903 973 928 48 611 387 144 500 647 32 432 528 643 365 600 494 5 381 858 686 481 165 155 799 651 611 482 465 330 991 179 186 249 271 724 398 828 912 764 384 706 536 287 161 294 928 267 927 799 24 593 981 444 784 685 18 827 286 60 299 312 814 375 967 364 885 739 766 976 57 322 784 170 566 619 654 669 148 635 690 63 779 986 458 637 95 430 715 940 39 863 574 281 470 554 807 677 296 447 695 315 46 600 407 70 249 335 856 295 289 22 889 225 215 697 618 541 544 763 52 94 825 760 30 738 301 355 759 118 630 593 444 388 835 826 434 281 749 54 370 684 200 207 799 658 180 25 276 363 995 748 109 542 328 443 286 483 222 305 551 249 566 570 16 754 411 432 155 735 963 649 620 295 600 655 435 616 774 773 709 179 837 546 979 832 274 869 974 820 802 200 703 14 487 659 131 567 732 265 363 658 185 995 323 694 116 765 56 739 156 744 438 66 713 102 210 44 258 690 135 710 263 385 355 641 455 630 3 694 634 192 858 217 166 487 262 356 868 33 563 585 750 795 488
23
491 531 93 257 751 699 508 96 587 836 254 854 568 792 327 253 381 654 730 104 856 490 223
726
510 735 540 744 52 830 846 926 271 193 742 750 53 508 998 504 945 225 55 651 40 340 763 145 757 86 352 977 28 630 425 80 455 240 720 537 443 584 380 172 700 472 281 697 411 866 831 810 12 122 632 96 923 102 327 470 240 675 537 956 698 983 826 795 747 139 425 577 442 761 722 787 911 719 367 472 283 685 784 907 664 539 357 761 207 672 173 499 982 402 487 777 357 504 870 379 272 462 946 651 591 841 564 639 271 28 661 675 154 245 839 864 299 957 678 358 149 505 824 414 322 957 797 811 259 954 370 535 157 719 881 811 845 801 822 472 644 42 304 37 122 286 549 429 436 692 384 878 93 432 39 191 494 879 979 360 996 359 594 522 107 880 73 326 430 259 60 487 2 416 56 466 887 112 896 462 629 313 290 564 1000 644 903 397 82 531 615 253 388 366 185 606 523 717 443 90 566 687 972 613 310 333 18 187 766 652 410 950 92 163 576 772 544 863 875 167 341 1 970 859 51 620 80 60 660 833 796 884 648 374 212 408 496 291 465 200 909 957 858 436 909 125 259 786 460 524 834 611 890 397 666 402 408 860 565 336 229 97 545 436 834 428 266 912 353 730 467 644 564 3 371 249 348 519 281 992 847 528 615 449 14 819 493 863 992 718 152 802 666 730 24 239 704 825 376 998 718 159 178 566 355 400 130 566 46 553 624 754 942 587 94 714 57 638 303 416 278 911 863 897 915 214 104 533 250 189 856 649 671 393 901 384 764 274 559 372 331 780 782 899 366 560 885 533 583 120 879 365 567 255 421 953 81 326 32 380 548 578 800 166 272 762 231 458 934 757 731 225 913 129 581 763 106 386 318 771 721 444 159 652 450 200 129 45 394 955 44 461 107 782 551 367 758 969 179 997 810 539 262 545 338 67 552 664 979 440 152 66 60 533 640 143 739 185 533 855 995 594 901 804 199 238 306 511 255 344 259 765 293 89 421 87 108 478 239 77 448 651 663 356 137 901 539 450 805 20 727 992 54 763 887 101 33 343 574 245 847 660 822 679 412 327 124 442 518 697 625 949 884 326 239 104 468 950 496 968 887 201 662 266 346 643 898 59 215 726 197 479 568 758 551 846 830 257 314 912 128 934 614 937 673 741 195 223 741 730 368 883 710 694 513 220 454 831 167 571 988 787 911 530 716 595 869 528 619 28 788 395 118 699 351 505 484 512 873 735 38 617 322 56 227 678 618 631 189 218 151 324 316 557 845 847 387 310 274 581 950 734 43 960 362 987 158 943 726 744 137 912 479 244 119 374 429 767 511 389 650 903 487 927 966 17 487 25 695 73 33 560 917 506 971 459 736 175 496 688 246 658 541 998 222 200 885 279 718 231 536 340 4 993 508 732 454 358 869 895 624 913 843 250 621 144 454 284 588 947 231 843 671 439 335 352 152 768 982 681 182 520 816 603 112 381 286 755 390 139 944 404 606 445 499 569 871 186 798 775 256 334 942 826 732 42 913 102 390 236 622 910 919 536 327 812 65 994 136 370 275 117 498 203 631 507 776 953 959 15 192 346 69 509 381 324 921 598 333 271 444 550 772 759 330 777 889 437 423 59 529 693 238 121 153 48 935 629 457 104 900 804 620 738 967 484 266 895 524 367
726
762 609 817 96 33 621 937 254 268 283 105 680 416 361 442 113 426 671 246 250 829 831 593 506 788 661 906 423 951 795 343 287 965 584 925 420 655 556 396 678 108 64 940 82 230 521 945 453 850 234 730 703 250 377 675 691 746 684 231 578 716 175 935 333 570 847 436 355 640 192 812 459 373 624 211 686 908 944 780 826 456 725 621 795 572 234 611 89 611 903 841 857 297 410 59 914 371 929 348 978 107 151 328 681 209 357 169 255 694 508 191 218 251 11 147 285 966 735 210 493 153 844 490 575 914 37 200 805 218 535 373 733 797 644 960 557 29 253 879 268 793 604 890 953 495 566 500 146 498 841 10 85 462 273 984 579 158 244 35 52 170 971 360 438 229 407 774 409 56 887 769 534 504 981 51 532 512 564 615 348 895 255 350 426 616 461 880 171 739 631 16 754 692 994 885 701 516 721 244 397 625 33 9 208 464 357 539 104 372 965 77 902 540 855 656 590 385 109 977 497 843 118 732 187 662 188 154 961 85 248 244 523 584 91 91 136 536 503 703 233 875 242 4 353 109 342 610 732 466 793 440 144 809 34 908 500 297 23 244 165 976 230 412 673 971 158 688 143 328 682 48 600 518 323 715 468 324 528 351 97 746 226 234 983 151 955 33 599 540 202 812 133 486 164 780 190 216 93 909 200 475 693 127 360 886 639 795 225 650 97 856 305 907 475 133 791 826 499 586 135 250 512 303 84 783 284 806 647 978 382 922 948 453 448 130 649 221 58 141 959 724 636 227 753 294 409 910 646 599 124 287 430 314 222 949 8 438 460 204 994 770 60 77 420 304 638 213 474 203 315 426 119 2 68 617 528 194 195 191 128 683 11 20 333 382 631 278 373 69 303 348 791 31 404 206 891 63 15 697 952 935 538 925 772 240 592 454 442 642 17 363 740 827 735 91 579 885 50 805 886 674 992 117 152 81 768 600 428 934 113 820 756 148 994 276 671 416 323 770 971 580 276 862 968 889 965 999 434 980 468 755 304 245 306 167 360 706 788 255 500 518 792 264 241 19 805 541 990 537 749 191 229 750 877 547 955 940 291 722 989 745 475 137 929 344 196 84 728 502 477 489 544 6 69 489 26 852 481 726 952 659 392 789 653 348 388 834 639 175 304 160 197 152 428 621 37 277 301 903 303 955 689 625 73 623 751 805 339 5 655 511 968 977 696 747 730 574 388 940 462 273 739 388 4 625 274 839 243 740 667 553 152 25 480 195 775 824 445 664 511 229 381 279 53 153 581 33 844 710 463 494 542 802 441 769 632 79 248 743 653 793 621 901 770 909 506 139 712 213 500 489 619 593 628 671 721 960 412 308 950 395 961 308 687 292 360 964 638 304 772 430 834 588 697 556 984 151 563 705 442 677 824 348 745 40 789 94 21 785 113 463 190 200 790 154 773 178 809 226 8 519 502 135 74 646 84 509 234 454 382 158 99 674 72 469 641 689 422 834 219 514 973 388 247 5 13 858 62 657 519 362 911 608 777 262 265 953 595 193 279 562 706 170 206 755 649 350 857 902 280 564 503 264 798 392 683 556 545 17 764 97 859 733 409 262 96 993 932 111 322 100 240 926 306 221 256 742 644 110 41 83 172 741 448 697 685
381
666 918 966 232 721 596 557 389 398 312 824 986 513 202 607 206 557 884 848 376 368 197 510 915 616 927 962 447 758 426 667 570 26 582 856 792 238 298 650 126 525 859 181 884 156 728 446 308 574 477 104 998 507 804 198 690 894 341 973 775 876 287 413 959 657 794 22 167 476 620 142 746 970 756 280 240 534 282 581 46 298 448 34 668 878 458 370 140 251 375 420 357 157 156 282 321 953 258 316 783 541 34 771 219 697 389 951 798 997 683 894 224 171 75 205 4 752 385 719 989 447 235 24 886 701 411 351 918 771 227 516 909 639 165 39 992 118 34 210 826 639 924 136 825 602 728 906 641 355 304 497 78 411 425 640 388 753 812 72 597 582 916 983 220 673 526 80 490 230 38 156 629 537 183 589 979 470 601 415 269 236 109 875 559 793 295 176 645 114 828 62 912 440 414 650 996 472 504 620 310 555 456 328 128 531 644 860 711 1 987 632 172 497 963 240 244 768 442 442 376 134 138 602 281 104 446 103 24 897 395 805 631 986 744 821 599 762 598 823 7 576 160 309 296 235 955 648 548 409 239 147 158 446 900 36 185 257 883 448 109 796 313 925 883 737 5 141 576 384 338 760 456 197 929 291 28 253 278 363 106 172 767 181 648 871 436 116 647 959 421 186 185 265 200 431 507 774 759 366 918 881 529 149 396 245 510 703 63 432 315 236 993 576 296 263 170 217 639 541 178 962 763 700 543 236 260 69 744 5 920 773 57 881 892 987 549 714 799 48 576 868 888 600 170 867 176 890 825 986 626 964 689 816 576 497 741 112 985 95 530 275 275 628 486 498 755 117 123 537 18 732 657 254 535 698 530 927 716 624 575 192
stdout
copy 
4
7
6
8
8
https://ideone.com/8iTK1Y
language:
C++14 (gcc 8.3)
created:
6 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!