結果
問題 | No.742 にゃんにゃんにゃん 猫の挨拶 |
ユーザー |
|
提出日時 | 2018-10-05 22:20:42 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 14 ms / 2,500 ms |
コード長 | 2,356 bytes |
コンパイル時間 | 1,220 ms |
コンパイル使用メモリ | 124,220 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-12 13:57:39 |
合計ジャッジ時間 | 1,835 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 16 |
ソースコード
#define _USE_MATH_DEFINES#include <cstdio>#include <iostream>#include <sstream>#include <fstream>#include <iomanip>#include <algorithm>#include <cmath>#include <complex>#include <string>#include <vector>#include <array>#include <list>#include <queue>#include <stack>#include <set>#include <map>#include <bitset>#include <numeric>#include <limits>#include <climits>#include <cfloat>#include <functional>#include <iterator>#include <memory>#include <regex>using namespace std;class BinaryIndexedTree{private:int n;vector<int> data;public:BinaryIndexedTree(int n){ // コンストラクタthis->n = n;data.assign(n+1, 0);}void add(int k, int x){ // k番目の要素にxを加算する++ k;while(k <= n){data[k] += x;k += k & -k;}}int sum(int k){ // 区間[0,k]の総和を返す++ k;int ret = 0;while(k > 0){ret += data[k];k -= k & -k;}return ret;}int sum(int a, int b){ // 区間[a,b]の総和を返すreturn sum(b) - sum(a-1);}int upper_bound(int x){ // 総和が初めてxを超える位置を返す(ただし、各位置の数値が非負数であることを前提とする)int b = 1;while(b < n)b *= 2;int a = 0;while(b > 0){if(a+b <= n && x >= data[a+b]){x -= data[a+b];a += b;}b /= 2;}return (a < n)? a : -1;}int lower_bound(int x){ // 総和が初めてx以上になる位置を返す(ただし、各位置の数値が非負数であることを前提とする)return upper_bound(x-1);}};int inversionNumber(const vector<int>& v){int n = v.size();vector<pair<int, int> > p(n);for(int i=0; i<n; ++i)p[i] = make_pair(v[i], i);sort(p.rbegin(), p.rend());BinaryIndexedTree bit(n);int ans = 0;for(int i=0; i<n; ++i){ans += bit.sum(p[i].second);bit.add(p[i].second, 1);}return ans;}int main(){int n;cin >> n;vector<int> v(n);for(int i=0; i<n; ++i)cin >> v[i];int ans = inversionNumber(v);cout << ans << endl;return 0;}