結果

問題 No.956 Number of Unbalanced
ユーザー risujirohrisujiroh
提出日時 2019-12-19 01:10:17
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 437 ms / 2,000 ms
コード長 4,482 bytes
コンパイル時間 2,376 ms
コンパイル使用メモリ 181,748 KB
実行使用メモリ 23,332 KB
最終ジャッジ日時 2023-09-21 04:38:57
合計ジャッジ時間 9,803 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
5,460 KB
testcase_01 AC 3 ms
5,344 KB
testcase_02 AC 4 ms
5,360 KB
testcase_03 AC 3 ms
5,544 KB
testcase_04 AC 4 ms
5,356 KB
testcase_05 AC 4 ms
5,376 KB
testcase_06 AC 277 ms
22,512 KB
testcase_07 AC 307 ms
22,244 KB
testcase_08 AC 258 ms
22,388 KB
testcase_09 AC 199 ms
22,080 KB
testcase_10 AC 256 ms
21,856 KB
testcase_11 AC 360 ms
23,004 KB
testcase_12 AC 280 ms
22,532 KB
testcase_13 AC 177 ms
22,816 KB
testcase_14 AC 437 ms
23,332 KB
testcase_15 AC 173 ms
22,708 KB
testcase_16 AC 288 ms
23,008 KB
testcase_17 AC 160 ms
22,704 KB
testcase_18 AC 436 ms
23,252 KB
testcase_19 AC 176 ms
23,292 KB
testcase_20 AC 435 ms
23,312 KB
testcase_21 AC 176 ms
22,776 KB
testcase_22 AC 160 ms
22,660 KB
testcase_23 AC 286 ms
23,072 KB
testcase_24 AC 177 ms
22,820 KB
testcase_25 AC 271 ms
21,980 KB
testcase_26 AC 173 ms
22,000 KB
testcase_27 AC 242 ms
22,008 KB
testcase_28 AC 273 ms
21,984 KB
testcase_29 AC 434 ms
23,236 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

string to_string(string s) { return '"' + s + '"'; }
string to_string(bool b) { return b ? "true" : "false"; }
template <size_t N> string to_string(bitset<N> bs) {
  string res;
  for (size_t i = 0; i < N; ++i) res += '0' + bs[i];
  return res;
}
string to_string(vector<bool> v) {
  string res = "{";
  for (bool e : v) res += to_string(e) + ", ";
  return res += "}";
}

template <class T, class U> string to_string(pair<T, U> p);
template <class C> string to_string(C c) {
  string res = "{";
  for (auto e : c) res += to_string(e) + ", ";
  return res += "}";
}
template <class T, class U> string to_string(pair<T, U> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

void debug() { cerr << '\n'; }
template <class Head, class... Tail> void debug(Head head, Tail... tail) {
  cerr << ' ' << to_string(head), debug(tail...);
}
#ifdef LOCAL
#define DEBUG(...) cerr << "[" << #__VA_ARGS__ << "]:", debug(__VA_ARGS__)
#else
#define DEBUG(...)
#endif

template<class T, T Op(T, T), T E(), class U, T Ap(T, U), U Cp(U, U), U Id()>
struct SegmentTree {
  const int n;
  vector<T> t;
  vector<U> u;
  SegmentTree(int _n) : n(_n), t(2 * n, E()), u(n, Id()) {}
  T& operator[](int i) { return t[i + n]; }
  void build() {
    for (int i = n - 1; i >= 1; --i) t[i] = Op(t[2 * i], t[2 * i + 1]);
  }
  void push() { for (int i = 1; i < n; ++i) push(i); }
  void apply(int i, U f) {
    t[i] = Ap(t[i], f);
    if (i < n) u[i] = Cp(u[i], f);
  }
  void push(int i) {
    if (u[i] == Id()) return;
    apply(2 * i, u[i]);
    apply(2 * i + 1, u[i]);
    u[i] = Id();
  }
  void push(int l, int r) {
    for (int hl = __lg(l + n), hr = __lg(r - 1 + n); hr > 0; --hl, --hr) {
      int al = (l + n) >> hl, ar = (r - 1 + n) >> hr;
      if (al < n) push(al);
      if (ar != al) push(ar);
    }
  }
  T acc(int l, int r) {
    push(l, r);
    T a = E(), b = E();
    for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
      if (l & 1) a = Op(a, t[l++]);
      if (r & 1) b = Op(t[--r], b);
    }
    return Op(a, b);
  }
  T get(int i) { return acc(i, i + 1); }
  void act(int l, int r, U f) {
    push(l, r);
    for (int i = l + n, j = r + n; i < j; i >>= 1, j >>= 1) {
      if (i & 1) apply(i++, f);
      if (j & 1) apply(--j, f);
    }
    l = (l + n) >> __builtin_ctz(l + n);
    while (l >>= 1) t[l] = Op(t[2 * l], t[2 * l + 1]);
    r = (r + n) >> __builtin_ctz(r + n);
    while (r >>= 1) t[r] = Op(t[2 * r], t[2 * r + 1]);
  }
  void set(int i, T a) {
    push(i, i + 1);
    t[i += n] = a;
    while (i >>= 1) t[i] = Op(t[2 * i], t[2 * i + 1]);
  }
};

struct T { long long v, c; };
T add(T a, T b) { return {a.v + b.v, a.c + b.c}; }
T zero() { return {0, 0}; }
T add(T a, long long f) { return {a.v + f * a.c, a.c}; }
long long add(long long f, long long g) { return f + g; }
long long zeroll() { return 0; }

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  vector<int> a(n);
  for (auto&& e : a) {
    cin >> e;
    --e;
  }
  vector< vector<int> > idx(1e5);
  for (int i = 0; i < n; ++i) {
    idx[a[i]].push_back(i);
  }
  SegmentTree<T, add, zero, long long, add, add, zeroll> st(2 * n + 1);
  SegmentTree<T, add, zero, long long, add, add, zeroll> sum(2 * n + 1);
  for (int i = 0; i <= 2 * n; ++i) {
    st[i] = {0, i};
    sum[i] = {0, 1};
  }
  st.build();
  sum.build();
  long long res = 0;
  for (int v = 0; v < 1e5; ++v) {
    if (idx[v].empty()) {
      continue;
    }
    DEBUG(v, idx[v]);
    vector<int> b;
    for (int t = 0; t < (int)idx[v].size(); ++t) {
      b.push_back(-(idx[v][t] - (t ? idx[v][t - 1] : -1) - 1));
      b.push_back(1);
    }
    b.push_back(-(n - idx[v].back() - 1));
    DEBUG(b);
    reverse(begin(b), end(b));
    int t = n;
    st.set(t, {t, t});
    sum.set(t, {1, 1});
    for (int e : b) {
      if (e == 1) {
        ++t;
        res += sum.acc(0, t).v;
        st.set(t, {st.get(t).v + t, t});
        sum.set(t, {sum.get(t).v + 1, 1});
      } else {
        res += sum.acc(0, t + e).v * -e + sum.acc(t + e, t).v * (t - 1) - st.acc(t + e, t).v;
        st.act(t + e, t, 1);
        sum.act(t + e, t, 1);
        t += e;
      }
    }
    t = n;
    for (int e : b) {
      if (e == 1) {
        ++t;
        st.set(t, {st.get(t).v - t, t});
        sum.set(t, {sum.get(t).v - 1, 1});
      } else {
        st.act(t + e, t, -1);
        sum.act(t + e, t, -1);
        t += e;
      }
    }
  }
  cout << res << '\n';
}
0