結果

問題 No.121 傾向と対策：門松列（その２）
ユーザー なおなお
提出日時 2015-01-09 00:33:58
言語 C++11
(gcc 11.4.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 1,081 bytes
コンパイル時間 1,619 ms
コンパイル使用メモリ 170,472 KB
実行使用メモリ 104,980 KB
最終ジャッジ日時 2024-07-05 18:33:56
合計ジャッジ時間 8,943 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 AC 571 ms
13,148 KB
testcase_04 AC 2,647 ms
104,980 KB
testcase_05 AC 567 ms
13,016 KB
testcase_06 AC 538 ms
11,120 KB
testcase_07 AC 544 ms
11,144 KB
testcase_08 AC 604 ms
13,024 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
#define ITER(c)             __typeof__((c).begin())
#define FOREACH(it, c)      for (ITER(c) it=(c).begin(); it != (c).end(); ++it)
#define REP(i, n)           for(int(i)=0;(i)<(n);++(i))
const int MOD = 1000000007;

int A[1000100];
int N;
int k = 1;

template<class _T>struct BIT{
    int N;vector<_T>bit;
    BIT(int n):bit(n+1){N=n;}
    void add(int i,_T v){for(int x=i;x<=N;x+=x&-x)bit[x]+=v;}
    _T sum(int i){_T r=0;for(int x=i;x>0;x-=x&-x)r+=bit[x];return r;}
    _T sum(int l,int r){return sum(r)-sum(l-1);}
};

ll solve(){
    BIT<int> bit(N);
    ll sum = 0;
    REP(i,N){
        sum += (ll)bit.sum(1,A[i]-1) * bit.sum(A[i]+1,k);
        bit.add(A[i],1);
    }
    return sum;
}

int main(){
    cin >> N;
    set<int> s;
    REP(i,N){ cin >> A[i]; s.insert(A[i]); }
    map<int,int> m;
    FOREACH(it,s) m[*it] = k++;
    REP(i,N) A[i] = m[A[i]];

    ll sum = solve();
    reverse(A,A+N);
    sum += solve();
    cout << sum << endl;
    return 0;
}
0