結果

問題 No.742 にゃんにゃんにゃん　猫の挨拶
コンテスト
ユーザー edamame882
提出日時 2019-07-26 00:03:04
言語 C++14
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 36 ms / 2,500 ms
コード長 1,834 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,034 ms
コンパイル使用メモリ 190,980 KB
実行使用メモリ 7,296 KB
最終ジャッジ日時 2024-07-02 06:20:49
合計ジャッジ時間 2,964 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

//repetition
#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)

//container util
#define all(x) (x).begin(),(x).end()

//typedef
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VLL;
typedef vector<VLL> VVLL;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;

//const value
//const ll MOD = 1e9 + 7;
//const int dx[] = {0,1,0,-1};//{0,0,1,1,1,-1,-1,-1};
//const int dy[] = {1,0,-1,0};//{1,-1,0,1,-1,0,1,-1};

//conversion
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
inline ll toLL(string s) {ll v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}


struct BIT{
  int n;
  VI nodes;
  void init(int N){
    nodes.resize(N+1,0);
    n = N;
  }
  void add(int i, int x){
    for(int idx = i; idx <= n; idx += idx & (-idx)){
      nodes[idx] += x;
    }
  }

  ll sum(int x){
    ll res = 0;
    for(int idx = x; idx > 0 ; idx -= idx & (-idx)){
      res += nodes[idx];
    }
    return res;
  }

};
VI comp(vector<PII> & m){
  vector<PII> origin(m);
  sort(all(m));
  map<PII,int> mp;
  rep(i,m.size()){
    mp[m[i]] = i+1;
  }
  VI res;
  rep(i,m.size()){
    res.push_back(mp[origin[i]]);
  }
  return res;
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  VI m(n);
  vector<PII> mp;
  map<int,int> cnt;
  rep(i,n){
    cin >> m[i];
    cnt[m[i]]++;
    mp.push_back({m[i],i});
  }
  VI v = comp(mp);
  ll ans = 0;
  BIT bit;
  bit.init(v.size());

  rep(i,v.size()){
    ans += i - bit.sum(v[i]);
    bit.add(v[i],1);
  }

  for(auto x: cnt){
    ans += x.second * (x.second - 1) / 2;
  }
  cout << ans << endl;
  return 0;
}
0