結果

問題 No.956 Number of Unbalanced
コンテスト
ユーザー kroton
提出日時 2019-12-13 09:35:11
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 264 ms / 2,000 ms
コード長 3,601 bytes
コンパイル時間 1,378 ms
コンパイル使用メモリ 114,916 KB
実行使用メモリ 17,920 KB
最終ジャッジ日時 2024-06-26 20:32:52
合計ジャッジ時間 6,130 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 6
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <vector>
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define fst first
#define snd second

/* clang-format off */
template <class T, size_t D> struct _vec { using type = vector<typename _vec<T, D - 1>::type>; };
template <class T> struct _vec<T, 0> { using type = T; };
template <class T, size_t D> using vec = typename _vec<T, D>::type;
template <class T> vector<T> make_v(size_t size, const T& init) { return vector<T>(size, init); }
template <class... Ts> auto make_v(size_t size, Ts... rest) { return vector<decltype(make_v(rest...))>(size, make_v(rest...)); }
template <class T> inline void chmin(T &a, const T& b) { if (b < a) a = b; }
template <class T> inline void chmax(T &a, const T& b) { if (b > a) a = b; }
/* clang-format on */

template <class T>
struct time_array {
 private:
  int t;
  vector<int> ts;
  vector<T> v;

 public:
  time_array() {
  }
  time_array(int n)
      : t(0), ts(n, 0), v(n) {
  }

  T& operator[](int i) {
    if (ts[i] < t) {
      ts[i] = t;
      v[i] = T{};
    }
    return v[i];
  }

  int size() const {
    return v.size();
  }

  void clear() {
    ++t;
  }
};

template <class T>
struct time_fenwick_tree {
  time_array<T> x;
  time_fenwick_tree(int n)
      : x(n + 1) {
  }
  void add(int k, T a) {
    for (++k; k < x.size(); k += k & -k) x[k] += a;
  }
  void add(int l, int r, T a) {
    add(l, a);
    add(r, -a);
  }
  T sum(int k) {
    T s = 0;
    for (; k > 0; k &= k - 1) s += x[k];
    return s;
  }
  void clear() {
    x.clear();
  }
};

struct poly_bit {
 private:
  int n;
  time_fenwick_tree<ull> bit2, bit1, bit0;

  // c2 * k^2 + c1 * k + c0
  ull sum(ull k) {
    ull c2 = bit2.sum(k + 1);
    ull c1 = bit1.sum(k + 1);
    ull c0 = bit0.sum(k + 1);
    return c2 * k * k + c1 * k + c0;
  }

 public:
  poly_bit(int n_)
      : n(n_), bit2(n), bit1(n), bit0(n) {
  }

  // [l, r) += x
  void add(ll l, ll r) {
    // [l, r)
    bit2.add(l, r, 1);
    bit1.add(l, r, 3 - 2 * l);
    bit0.add(l, r, l * l - 3 * l + 2);
    // [r, inf)
    bit1.add(r, 2 * (r - l));
    bit0.add(r, l * l - 3 * l - r * r + 3 * r);
  }

  // [l, r)
  ll sum(int l, int r) {
    return (sum(r - 1) - sum(l - 1)) / 2;
  }

  void clear() {
    bit2.clear();
    bit1.clear();
    bit0.clear();
  }
};

const int M = 210000, GETA = 105000;

ll solve(const vector<int>& A) {
  int N = A.size();
  map<int, vector<int>> mp;
  for (int i = 0; i < N; i++) mp[A[i]].push_back(i + 1);
  ll res = 0;
  poly_bit pbit(M);
  for (auto& entry : mp) {
    vector<int> ind = entry.snd;
    ind.insert(ind.begin(), -1);
    ind.push_back(N + 1);
    vector<pair<int, int>> ps;
    for (int i = 1, c = 0; i < ind.size(); i++, c++) {
      int pre = 2 * c - ind[i - 1];
      int cur = 2 * (c + 1) - ind[i];
      ps.emplace_back(cur - 1, pre);
      if (i + 1 < ind.size()) {
        ps.emplace_back(cur, cur + 1);
      }
    }
    for (auto p : ps) {
      int L = p.fst + GETA, R = p.snd + GETA;
      res += pbit.sum(L - 1, R - 1);
      pbit.add(L, R);
    }
    pbit.clear();
  }
  return res;
}

int main() {
#ifdef DEBUG
  ifstream ifs("in.txt");
  cin.rdbuf(ifs.rdbuf());
#endif
  int N;
  while (cin >> N) {
    vector<int> A(N);
    for (int& x : A) cin >> x;
    cout << solve(A) << endl;
  }
  return 0;
}
0