結果

問題 No.121 傾向と対策：門松列（その２）
ユーザー なお
提出日時 2015-01-09 00:33:58
言語 C++11（廃止可能性あり）
(gcc 13.3.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 6 WA * 3
権限があれば一括ダウンロードができます

ソースコード

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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
2