結果

問題 No.121 傾向と対策：門松列（その２）
コンテスト
ユーザー maine_honzuki
提出日時 2020-05-17 15:59:00
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2,332 ms / 5,000 ms
コード長 1,903 bytes
コンパイル時間 1,775 ms
コンパイル使用メモリ 179,296 KB
実行使用メモリ 163,368 KB
最終ジャッジ日時 2024-09-25 08:15:44
合計ジャッジ時間 8,964 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 9
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

template <typename T>
class BinaryIndexedTree {
    vector<T> data;
    int n;
    //
public:
    BinaryIndexedTree(int n_) : n(n_ + 2), data(n_ + 2, 0) {}
    T sum(int i) {
        T ret(0);
        for (int x = i + 1; x > 0; x -= x & -x)
            ret += data[x];
        return ret;
    }
    void add(int i, T a) {
        for (int x = i + 1; x <= n; x += x & -x) {
            data[x] += a;
        }
    }
};

int total, l[1000010] = {}, r[1000010] = {}, L[1000010] = {}, R[1000010] = {};
long long same_l[1000010], same_r[1000010], rem[1000010];

int main() {
    int N, A[1000010];
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }

    map<int, vector<int>> mp;
    for (int i = 0; i < N; i++) {
        mp[A[i]].emplace_back(i);
    }

    BinaryIndexedTree<int> bit1(N);

    for (auto& p : mp) {
        for (int i = p.second.size() - 1; i >= 0; i--) {
            int x = p.second[i];
            l[x] = bit1.sum(x);
            r[x] = total - l[x];
            bit1.add(x, 1);
            same_l[x] = i;
            same_r[x] = p.second.size() - 1 - i;
        }
        total += p.second.size();
    }


    total = 0;
    BinaryIndexedTree<int> bit2(N);

    for (auto it = mp.rbegin(); it != mp.rend(); it++) {
        auto p = *it;
        for (int i = p.second.size() - 1; i >= 0; i--) {
            int x = p.second[i];
            L[x] = bit2.sum(x);
            R[x] = total - L[x];
            bit2.add(x, 1);
        }
        total += p.second.size();
    }

    for (int i = 1; i < N; i++) {
        rem[i] = rem[i - 1] + same_r[i - 1] - same_l[i];
    }

    for (int i = 0; i < N; i++) {
        rem[i] -= same_l[i] * same_r[i];
    }

    long long ans = 0;
    for (int i = 0; i < N; i++) {
        ans += (long long)l[i] * r[i] + (long long)L[i] * R[i] - rem[i];
    }

    cout << ans << endl;
}
0