結果

問題 No.1300 Sum of Inversions
ユーザー rabimea
提出日時 2025-07-01 21:45:09
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,841 bytes
コンパイル時間 2,711 ms
コンパイル使用メモリ 209,488 KB
実行使用メモリ 181,960 KB
最終ジャッジ日時 2025-07-01 21:45:17
合計ジャッジ時間 8,235 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other TLE * 1 -- * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using ll = long long;
const ll Inf = 1e9L + 1;

struct FenwickTree {
  static constexpr int MaxN = Inf;
  static constexpr int IndexOffset = 1;
  static int Lowbit(int x) { return x&(-x); }
  std::unordered_map <int, ll> b;
  void Reset() { b = {}; }
  void Add(int p, ll x) {
    p += IndexOffset;
    for(; p <= MaxN + IndexOffset; p += Lowbit(p)) {
      b[p] += x;
    }
  }
  ll Query(int p) {
    p += IndexOffset;
    ll r = 0;
    for(; p; p -= Lowbit(p)) {
      r += b[p];
    }
    return r;
  }
};

// sum of a_i
ll Solve1(int n, std::vector <int> a, std::vector <int> orig_a) {
  ll r = 0;
  FenwickTree tree_cnt, tree_sum;
  for(int i = n - 1; i >= 0; i --) {
    ll cnt = tree_cnt.Query(a[i] - 1);
    ll sum = tree_sum.Query(a[i] - 1);
    r += ll(orig_a[i]) * sum;
    tree_cnt.Add(a[i], 1);
    tree_sum.Add(a[i], cnt);
  }
  return r;
}

// sum of a_j
ll Solve2(int n, std::vector <int> a) {
  FenwickTree tree;
  std::vector <int> cnt_lu(n), cnt_rd(n);
  for(int i = 0; i < n; i ++) {
    cnt_lu[i] = tree.Query(Inf) - tree.Query(a[i]);
    tree.Add(a[i], 1);
  }
  tree.Reset();
  for(int i = n - 1; i >= 0; i --) {
    cnt_rd[i] = tree.Query(a[i] - 1);
    tree.Add(a[i], 1);
  }
  ll r = 0;
  for(int i = 0; i < n; i ++) {
    r += ll(a[i]) * cnt_lu[i] * cnt_rd[i];
  }
  return r;
}

// sum of a_k
ll Solve3(int n, std::vector <int> a) {
  reverse(a.begin(), a.end());
  std::vector <int> orig_a = a;
  for(int &x : a) {
    x = Inf - x;
  }
  return Solve1(n, a, orig_a);
}

int main() {
  std::ios::sync_with_stdio(0);
  int n; std::cin >> n;
  std::vector <int> a(n);
  for(int i = 0; i < n; i ++) {
    std::cin >> a[i];
  }
  std::cout << Solve1(n, a, a) + Solve2(n, a) + Solve3(n, a) << '\n';
  // std::cout << Solve1(n, a, a) << '\n' << Solve2(n, a) << '\n' << Solve3(n, a) << '\n';
}
0