結果

問題 No.121 傾向と対策:門松列(その2)
ユーザー Min_25
提出日時 2016-07-12 23:43:59
言語 C++14
(gcc 9.2.0)
結果
AC  
実行時間 176 ms
コード長 2,129 Byte
コンパイル時間 832 ms
使用メモリ 15,180 KB
最終ジャッジ日時 2020-01-19 03:20:53

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
99_system_test1.txt AC 4 ms
3,740 KB
99_system_test2.txt AC 8 ms
4,008 KB
99_system_test3.txt AC 4 ms
3,372 KB
2015 AC 76 ms
15,180 KB
happy AC 176 ms
14,992 KB
kadomatsu AC 124 ms
15,032 KB
new AC 136 ms
15,024 KB
year AC 164 ms
15,108 KB
yukicoder AC 152 ms
14,956 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