fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int MAX = 11;
  6.  
  7. int main() {
  8.     int tests;
  9.     cin >> tests;
  10.     for(int test = 0; test < tests; test++) {
  11.         int n;
  12.         cin >> n;
  13.         vector<int> a(n);
  14.         for(auto &i : a) {
  15.             cin >> i;
  16.         }
  17.         long long ans = 0;
  18.         for(int x = 1; x < MAX; x++) {
  19.             vector<int> b(n);
  20.             for(int i = 0; i < n; i++) {
  21.                 b[i] = (a[i] > x? 1 : -1);
  22.             }
  23.             int sum = n;
  24.             vector<int> pref(n);
  25.             for(int i = 0; i < n; i++) {
  26.                 pref[i] = sum;
  27.                 sum += b[i];
  28.             }
  29.             vector<int> cnt(2 * n + 1);
  30.             sum = n;
  31.             int j = 0;
  32.             for(int i = 0; i < n; i++) {
  33.                 if(a[i] == x) {
  34.                     while(j <= i) {
  35.                         cnt[pref[j]]++;
  36.                         j++;
  37.                     }
  38.                 }
  39.                 sum += b[i];
  40.                 ans += cnt[sum];
  41.             }
  42.         }
  43.         ans = 1ll * n * (n + 1) / 2 - ans;
  44.         cout << ans << '\n';
  45.     }
  46.     return 0;
  47. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
3
4
1 1 1 1
5
1 10 2 3 3
10
6 3 2 3 5 3 4 2 3 5
stdout
copy 
10
11
42
https://ideone.com/XcPfc7
language:
C++ (gcc 8.3)
created:
43 days 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!