結果

問題 No.121 傾向と対策:門松列(その2)
ユーザー Min_25
提出日時 2016-07-12 23:43:59
言語 C++14
(gcc 8.2.0)
結果
AC  
実行時間 181 ms
コード長 2,129 Byte
コンパイル時間 782 ms
使用メモリ 13,300 KB
最終ジャッジ日時 2019-07-25 03:50:16

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
99_system_test1.txt AC 9 ms
6,868 KB
99_system_test2.txt AC 13 ms
6,872 KB
99_system_test3.txt AC 4 ms
6,872 KB
2015 AC 77 ms
13,300 KB
happy AC 181 ms
13,296 KB
kadomatsu AC 119 ms
13,300 KB
new AC 132 ms
13,300 KB
year AC 155 ms
13,300 KB
yukicoder AC 149 ms
13,300 KB
テストケース一括ダウンロード

ソースコード

diff #
#pragma GCC optimize ("O3")
#pragma GCC target ("avx") // yukicoder
// #pragma GCC target ("sse4") // SPOJ, codechef

#include <cstdio>
#include <cassert>
#include <cmath>
#include <cstring>

#include <complex>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <functional>
#include <tuple>

#define _rep(_1, _2, _3, _4, name, ...) name
#define rep2(i, n) rep3(i, 0, n)
#define rep3(i, a, b) rep4(i, a, b, 1)
#define rep4(i, a, b, c) for (int i = int(a); i < int(b); i += int(c))
#define rep(...) _rep(__VA_ARGS__, rep4, rep3, rep2, _)(__VA_ARGS__)

using namespace std;

using i8 = signed char;
using i64 = long long;
using u8 = unsigned char;
using u32 = unsigned;
using u64 = unsigned long long;
using f80 = long double; 

#define getchar getchar_unlocked

int get_int() {
  int n, c, sign = 0;
  while ((c = getchar()) < '-');
  if (c == '-') sign = 1, n = 0;
  else n = c - '0';
  while ((c = getchar()) >= '0') n = n * 10 + c - '0';
  return sign ? -n : n;
}

i64 A[1000010];
int fenwick[1000010];

inline void add(int N, int n) {
  n += 1;
  while (n <= N) {
    fenwick[n] += 1;
    n += n & -n;
  }
}

inline int sum(int, int n) {
  int ret = 0;
  n += 1;
  while (n) {
    ret += fenwick[n];
    n &= n - 1;
  }
  return ret;
}

void solve() {
  int N;
  while (~scanf("%d", &N)) {
    rep(i, N) A[i] = i64(get_int()) << 32 | i;
    sort(A, A + N);

    fill(fenwick, fenwick + N + 1, 0);

    int c = 0, prev_v = 0, prev_j = 0;
    i64 cumu = 0, ans = 0;
    rep(i, N) {
      int j = A[i], v = A[i] >> 32;
      if (v == prev_v) {
        ++c;
      } else {
        c = 0, cumu = 0;
      }
      int left = sum(N, j), right = i - left;
      ans += i64(j - left) * (N - 1 - j - right);
      ans += i64(left - c) * right;
      if (v == prev_v) cumu += i64(c) * (j - prev_j - 1);
      ans -= cumu;
      cumu += j - left;
      add(N, j);
      prev_j = j, prev_v = v;
    }
    printf("%lld\n", ans);
  }
}

int main() {
  clock_t beg = clock();
  solve();
  clock_t end = clock();
  fprintf(stderr, "%.3f sec\n", double(end - beg) / CLOCKS_PER_SEC);
  return 0;
}
0