SHARE
TWEET

Untitled

sonprao Feb 17th, 2019 81 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define FOR(i,a,b) for(i=a;i<=b;i++)
  3. using namespace std;
  4. long long T,b[100005],a[100005],i,j,n,p,h,q;
  5. int main()
  6. {
  7.     ios_base::sync_with_stdio(false);
  8.     cin.tie(0);
  9.     map<int,int> map1;
  10.     cin>>T;
  11.     b[1]=2;
  12.     FOR(i,2,100005) b[i]=b[i-1]+i*(i+1);
  13.     FOR(q,1,T)
  14.     {
  15.         cin>>n;
  16.         FOR(i,1,n) cin>>a[i];
  17.         i=1;
  18.         j=1;
  19.         p=0;
  20.         map1.clear();
  21.         while (j<=n)
  22.         {
  23.             map1[a[i]]=true;
  24.             j=i+1;
  25.             if (i==n) {p+=1; break;}
  26.             while (map1.find(a[j])==map1.end())
  27.             {
  28.                 map1[a[j]]=j;
  29.                 j++;
  30.                 if (j>n) break;
  31.             }
  32.             //cout<<i<<" "<<j-1<<endl;
  33.             h=j-i;
  34.             //cout<<"a[j]="<<a[j]<<endl;
  35.             p+=h*h*(h+1)/2-b[h-1];
  36.             int k=j-map1[a[j]];
  37.             if (j>n) break;
  38.             p+=(k)*(k+1)/2;
  39.             if (k!=0) p-=1;
  40.             i=j;
  41.             map1.clear();
  42.         }
  43.         printf("%d\n",p);
  44.     }
  45.     return 0;
  46. }/*/
  47. 1
  48. 6
  49. 1 2 3 2 1 1
  50. */
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top