fork(2) download
copy 
  1. #include <stdio.h>
  2. #include <algorithm>
  3. #include <assert.h>
  4. #include <set>
  5. #include <map>
  6. #include <complex>
  7. #include <iostream>
  8. #include <time.h>
  9. #include <math.h>
  10. #include <stack>
  11. #include <stdlib.h>
  12. #include <memory.h>
  13. #include <bitset>
  14. #include <math.h>
  15. #include <string>
  16. #include <string.h>
  17. #include <queue>
  18. #include <vector>
  19.  
  20. using namespace std;
  21.  
  22. const int MaxN = 5e5 + 10;
  23. const int SHIFT = 5e5 + 10;
  24. const int INF = 1e9;
  25. const int MOD = 1e9 + 7;
  26.  
  27. struct Node {
  28.   int sum, add;
  29. } t[8 * SHIFT];
  30.  
  31. int n, a[MaxN];
  32. vector < int > c[MaxN];
  33.  
  34. void compress(int a[], int n) {
  35.   vector < int > b;
  36.   for (int i = 1; i <= n; ++i) {
  37.     b.push_back(a[i]);
  38.   }
  39.   sort(b.begin(), b.end());
  40.   b.resize(unique(b.begin(), b.end()) - b.begin());
  41.   for (int i = 1; i <= n; ++i) {
  42.     a[i] = lower_bound(b.begin(), b.end(), a[i]) - b.begin();
  43.   }
  44. }
  45.  
  46. void push(int v, int l, int r) {
  47.   if (t[v].add != 0) {
  48.     t[v].sum += (r - l + 1) * t[v].add;
  49.     if (l != r) {
  50.       t[v + v].add += t[v].add;
  51.       t[v + v + 1].add += t[v].add;
  52.     }
  53.     t[v].add = 0;
  54.   }
  55. }
  56.  
  57. void upd(int v, int L, int R, int l, int r, int val) {
  58.   push(v, L, R);
  59.   if (l > R || r < L) {
  60.     return;
  61.   }
  62.   if (l <= L && R <= r) {
  63.     t[v].add += val;
  64.     push(v, L, R);
  65.     return;
  66.   }
  67.   int M = (L + R) / 2;
  68.   upd(v + v, L, M, l, r, val);
  69.   upd(v + v + 1, M + 1, R, l, r, val);
  70.   t[v].sum = t[v + v].sum + t[v + v + 1].sum;
  71. }
  72.  
  73. int get(int v, int L, int R, int l, int r) {
  74.   push(v, L, R);
  75.   if (L == l && r == R) {
  76.     return t[v].sum;
  77.   }
  78.   int M = (L + R) / 2, res = 0;
  79.   push(v + v, L, M);
  80.   push(v + v + 1, M + 1, R);
  81.   if (r <= M) {
  82.     res += get(v + v, L, M, l, r);
  83.   } else if (l > M) {
  84.     res += get(v + v + 1, M + 1, R, l, r);
  85.   } else {
  86.     res += get(v + v, L, M, l, M) +
  87.       get(v + v + 1, M + 1, R, M + 1, r);
  88.   }
  89.   t[v].sum = t[v + v].sum + t[v + v + 1].sum;
  90.   return res;
  91. }
  92.  
  93. long long solve(vector < int > &occur) {
  94.   occur.push_back(n + 1);
  95.   vector < pair < int, int > > changes;
  96.   int r = SHIFT - 0, l = SHIFT - (occur[0] - 1);
  97.   changes.push_back(make_pair(l, r));
  98. //  cout << l - SHIFT << ' ' << r - SHIFT << endl;
  99.   upd(1, 1, 2 * SHIFT, l, r, +1);
  100.   long long ans = 0LL;
  101.   for (int i = 0; i + 1 < (int)occur.size(); ++i) {
  102.     int l = 2 * (i + 1) - (occur[i + 1] - 1) + SHIFT;
  103.     int r = 2 * (i + 1) - occur[i] + SHIFT;
  104.     for (int j = r - 1, add = 1; j >= l - 1 && add != 0; --j) {
  105.       add = get(1, 1, 2 * SHIFT, 1, j);
  106.       ans += add;
  107.     }
  108.     changes.push_back(make_pair(l, r));
  109.     upd(1, 1, 2 * SHIFT, l, r, +1);
  110.   }
  111.   for (int i = 0; i < (int)changes.size(); ++i) {
  112.     int l = changes[i].first, r = changes[i].second;
  113.     upd(1, 1, 2 * SHIFT, l, r, -1);
  114.   }
  115.   return ans;
  116. }
  117.  
  118. int main() {
  119. //  freopen("input.txt", "r", stdin);
  120.   ios::sync_with_stdio(false);
  121.   cin.tie(NULL);
  122.   cin >> n;
  123.   for (int i = 1; i <= n; ++i) {
  124.     cin >> a[i];
  125.   }
  126.   compress(a, n);
  127.   for (int i = 1; i <= n; ++i) {
  128.     c[a[i]].push_back(i);
  129.   }
  130.   long long ans = 0LL;
  131.   for (int i = 0; i < n; ++i) {
  132.     if (!c[i].empty()) {
  133.       ans += solve(c[i]);
  134.     }
  135.   }
  136.   cout << ans << '\n';
  137.   return 0;
  138. }
  139.  
Success #stdin #stdout 0s 42528KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/sssrlP
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
secret

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!