結果

問題 No.121 傾向と対策：門松列（その２）
コンテスト
ユーザー codershifth
提出日時 2015-10-12 19:31:09
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 2,000 ms / 5,000 ms
コード長 2,520 bytes
コンパイル時間 1,418 ms
コンパイル使用メモリ 172,516 KB
実行使用メモリ 78,176 KB
最終ジャッジ日時 2024-06-28 18:38:53
合計ジャッジ時間 6,323 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 9
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>

typedef long long ll;
typedef unsigned long long ull;

#define FOR(i,a,b) for(int (i)=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define RANGE(vec) (vec).begin(),(vec).end()

template <typename T>
class BIT
{
public:
    std::vector<T> data; // [1,n]
    BIT() {}
    BIT(int n) { init(n); }
    void init(int n) { data.resize((1LL<<(int)ceil(log2(n))), 0); }
    // a[i] += x                   O(log(n))
    void add(int i, int x)
    {
            int maxN = data.size()+1; // 2 冪
            for (int k = i+1; k <= maxN; k += (k & -k))
                data[k-1] += x;
    }
    // a[0]+...+a[i-1]             O(log(n))
    T sum(int i)
    {
            T s = 0;
            for (int k = i+1; k > 0; k -= (k & -k))
                s += data[k-1];
            return s;
    }
};

using namespace std;

//
// 愚直なやり方だと O(N^3) で TLE
//
class TrendAndCountermeasures_PineDecorationSequence2 {
public:
    void solve(void) {
            int N;
            cin>>N;

            map<int,int> conv; // mapping 用
            vector<int> A(N);
            REP(i,N)
            {
                cin>>A[i];
                conv[A[i]] = 0;
            }
            // A は一致しているかどうかが問題になるだけなので
            // 0...N-1 をマッピングして max(A) < N にする
            int k = 0;
            for (auto kv : conv)
                conv[kv.first] = k++;
            REP(i,N)
                A[i] = conv[A[i]];

            vector<int> L(N,0);
            vector<int> R(N,0);

            BIT<ll> bit1(N);
            BIT<ll> bit2(N);

            REP(i,N)
            {
                ++R[A[i]];
                bit2.add(A[i],1);
            }
            ll ret = 0;
            REP(i,N)
            {
                bit2.add(A[i],-1);
                ret += bit1.sum(A[i]-1)*bit2.sum(A[i]-1);
                ret += (i - bit1.sum(A[i])) * ((N-i-1) - bit2.sum(A[i]));
                bit1.add(A[i],1);
            }
            ll diff = 0;
            REP(i,N)
            {
                diff -= (ll)L[A[i]] * R[A[i]];
                ret -= diff;
                ++L[A[i]];
                --R[A[i]];
                diff += (ll)L[A[i]] * R[A[i]];
            }
            cout<<ret-diff<<endl;
    }
};

#if 1
int main(int argc, char *argv[])
{
        ios::sync_with_stdio(false);
        auto obj = new TrendAndCountermeasures_PineDecorationSequence2();
        obj->solve();
        delete obj;
        return 0;
}
#endif
0