fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. bool qf=false;      //fast io enabled/disabled
  4.  
  5. #define input       freopen("in.txt","r",stdin);
  6. #define output      freopen("out.txt","w",stdout);
  7. #define fast        ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);qf=true;
  8.  
  9. #define sc          scanf
  10. #define pr          printf
  11. #define whi         while
  12. #define ll          long long
  13. #define ull         unsigned long long
  14. #define lld         I64d
  15. #define ff          first
  16. #define ss          second
  17. #define vc          vector
  18. #define pb          push_back
  19. #define ite         iterator
  20. #define str         string
  21. #define bl          bool
  22. #define tr          true
  23. #define fl          false
  24. #define ct          continue
  25. #define endl        '\n'
  26. #define ret         return
  27. #define rsort(a)    greater<a>
  28. #define nl          if(qf==tr) pr("\n");else cout<<"\n";
  29. #define gcd(a,b)    __gcd(a,b)
  30. #define mod         1000000007
  31. #define tc          int t;if(qf==fl) scanf("%d",&t); else cin>>t;whi(t--)
  32. #define minof(a)    std::numeric_limits<a>::min()
  33. #define maxof(a)    std::numeric_limits<a>::max()
  34. #define setval(a,v) memset(a,v,sizeof(a));
  35.  
  36. #define all(c)      c.begin(),c.end()
  37. #define sz(c)       c.size()
  38. #define clr(c)      c.clear()
  39. #define fd(c,a)     c.find(a)
  40. #define bg(c)       c.begin()
  41. #define ed(c)       c.end()
  42. #define ins(c,a)    c.insert(a)
  43. #define rem(c,a)    c.erase(a)
  44.  
  45. int main()
  46. {
  47.     tc
  48.     {
  49.         register int n,i,j,k,a[2016],len,previans=0,val1,val2;
  50.         register int origlen,len1,len2,tmpans;
  51.         ll ans=0;
  52.         map <int,vc<int>> m;
  53.         vc <int>::ite it;
  54.         sc("%d",&n);
  55.         for(i=0;i<n;i++)
  56.         {
  57.             sc("%d",&a[i]);
  58.             m[a[i]].pb(i);
  59.         }
  60.         for(i=0;i<n;i++) m[a[i]].pb(n);
  61.         for(i=0;i<n-1;i++)
  62.         {
  63.             set <int> mark;
  64.             set <int>::ite it1,it2;
  65.             mark.insert(n);
  66.             tmpans=(n-i)*(n-i+1)/2;
  67.             for(j=i;j<n-1;j++)
  68.             {
  69.                 it=lower_bound(m[a[j]].begin(),m[a[j]].end(),j);
  70.                 if(fd(mark,*it)!=ed(mark) and *it!=n)
  71.                 {
  72.                     ans+=previans;
  73.                     ct;
  74.                 }
  75.                 for(;*it!=n;it++)
  76.                 {
  77.                     it2=mark.lower_bound(*it);
  78.                     if(it2==bg(mark)) val1=j-1;
  79.                     else
  80.                     {
  81.                         it1=it2;
  82.                         it1--;
  83.                         val1=*it1;
  84.                     }
  85.                     val2=*it2;
  86.                     len=val2-val1;
  87.                     len1=max(0,val2-*it);
  88.                     len2=max(0,*it-val1);
  89.                     tmpans-=((len*(len+1)/2)-(len1*(len1+1)/2)-(len2*(len2+1)/2));
  90.                     ins(mark,*it);
  91.                 }
  92.                 previans=tmpans;
  93.                 ans+=tmpans;
  94.             }
  95.         }
  96.         pr("%lld\n",ans);
  97.     }
  98.     ret 0;
  99. }
  100. /*
  101. 1
  102. 3
  103. 1 2 3
  104.  
  105. 1
  106. 5
  107. 1 1 2 2 2
  108. Answer --> 18
  109.  
  110. 1
  111. 4
  112. 1 2 2 2
  113. Answer --> 6
  114.  
  115. 2
  116. 3
  117. 1 2 3
  118. 4
  119. 1 2 1 2
  120.  
  121. 1
  122. 4
  123. 1 2 1 2
  124.  
  125. 1
  126. 10
  127. 2 8 5 1 10 5 9 9 3 5
  128. Answer --> 294
  129.  
  130. 1
  131. 7
  132. 1 4 6 2 1 2 4
  133. Answer --> 55
  134. */
  135.  
Success #stdin #stdout 0.2s 3468KB
comments (?)
stdin
copy 
1
1000
1 2 1 4 1 6 1 8 1 10 1 12 1 14 1 16 1 18 1 20 1 22 1 24 1 26 1 28 1 30 1 32 1 34 1 36 1 38 1 40 1 42 1 44 1 46 1 48 1 50 1 52 1 54 1 56 1 58 1 60 1 62 1 64 1 66 1 68 1 70 1 72 1 74 1 76 1 78 1 80 1 82 1 84 1 86 1 88 1 90 1 92 1 94 1 96 1 98 1 100 1 102 1 104 1 106 1 108 1 110 1 112 1 114 1 116 1 118 1 120 1 122 1 124 1 126 1 128 1 130 1 132 1 134 1 136 1 138 1 140 1 142 1 144 1 146 1 148 1 150 1 152 1 154 1 156 1 158 1 160 1 162 1 164 1 166 1 168 1 170 1 172 1 174 1 176 1 178 1 180 1 182 1 184 1 186 1 188 1 190 1 192 1 194 1 196 1 198 1 200 1 202 1 204 1 206 1 208 1 210 1 212 1 214 1 216 1 218 1 220 1 222 1 224 1 226 1 228 1 230 1 232 1 234 1 236 1 238 1 240 1 242 1 244 1 246 1 248 1 250 1 252 1 254 1 256 1 258 1 260 1 262 1 264 1 266 1 268 1 270 1 272 1 274 1 276 1 278 1 280 1 282 1 284 1 286 1 288 1 290 1 292 1 294 1 296 1 298 1 300 1 302 1 304 1 306 1 308 1 310 1 312 1 314 1 316 1 318 1 320 1 322 1 324 1 326 1 328 1 330 1 332 1 334 1 336 1 338 1 340 1 342 1 344 1 346 1 348 1 350 1 352 1 354 1 356 1 358 1 360 1 362 1 364 1 366 1 368 1 370 1 372 1 374 1 376 1 378 1 380 1 382 1 384 1 386 1 388 1 390 1 392 1 394 1 396 1 398 1 400 1 402 1 404 1 406 1 408 1 410 1 412 1 414 1 416 1 418 1 420 1 422 1 424 1 426 1 428 1 430 1 432 1 434 1 436 1 438 1 440 1 442 1 444 1 446 1 448 1 450 1 452 1 454 1 456 1 458 1 460 1 462 1 464 1 466 1 468 1 470 1 472 1 474 1 476 1 478 1 480 1 482 1 484 1 486 1 488 1 490 1 492 1 494 1 496 1 498 1 500 1 502 1 504 1 506 1 508 1 510 1 512 1 514 1 516 1 518 1 520 1 522 1 524 1 526 1 528 1 530 1 532 1 534 1 536 1 538 1 540 1 542 1 544 1 546 1 548 1 550 1 552 1 554 1 556 1 558 1 560 1 562 1 564 1 566 1 568 1 570 1 572 1 574 1 576 1 578 1 580 1 582 1 584 1 586 1 588 1 590 1 592 1 594 1 596 1 598 1 600 1 602 1 604 1 606 1 608 1 610 1 612 1 614 1 616 1 618 1 620 1 622 1 624 1 626 1 628 1 630 1 632 1 634 1 636 1 638 1 640 1 642 1 644 1 646 1 648 1 650 1 652 1 654 1 656 1 658 1 660 1 662 1 664 1 666 1 668 1 670 1 672 1 674 1 676 1 678 1 680 1 682 1 684 1 686 1 688 1 690 1 692 1 694 1 696 1 698 1 700 1 702 1 704 1 706 1 708 1 710 1 712 1 714 1 716 1 718 1 720 1 722 1 724 1 726 1 728 1 730 1 732 1 734 1 736 1 738 1 740 1 742 1 744 1 746 1 748 1 750 1 752 1 754 1 756 1 758 1 760 1 762 1 764 1 766 1 768 1 770 1 772 1 774 1 776 1 778 1 780 1 782 1 784 1 786 1 788 1 790 1 792 1 794 1 796 1 798 1 800 1 802 1 804 1 806 1 808 1 810 1 812 1 814 1 816 1 818 1 820 1 822 1 824 1 826 1 828 1 830 1 832 1 834 1 836 1 838 1 840 1 842 1 844 1 846 1 848 1 850 1 852 1 854 1 856 1 858 1 860 1 862 1 864 1 866 1 868 1 870 1 872 1 874 1 876 1 878 1 880 1 882 1 884 1 886 1 888 1 890 1 892 1 894 1 896 1 898 1 900 1 902 1 904 1 906 1 908 1 910 1 912 1 914 1 916 1 918 1 920 1 922 1 924 1 926 1 928 1 930 1 932 1 934 1 936 1 938 1 940 1 942 1 944 1 946 1 948 1 950 1 952 1 954 1 956 1 958 1 960 1 962 1 964 1 966 1 968 1 970 1 972 1 974 1 976 1 978 1 980 1 982 1 984 1 986 1 988 1 990 1 992 1 994 1 996 1 998 1 1000
stdout
copy 
166541750
https://ideone.com/hI99QG
language:
C++14 (gcc 8.3)
created:
7 years 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!