結果
問題 |
No.1604 Swap Sort:ONE
|
ユーザー |
|
提出日時 | 2021-07-31 03:15:22 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 4 ms / 2,000 ms |
コード長 | 1,865 bytes |
コンパイル時間 | 1,719 ms |
コンパイル使用メモリ | 169,140 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-16 06:34:12 |
合計ジャッジ時間 | 2,821 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define REP(i,n) for (int i = 0; i < (n); ++i) #define DREP(i,s,n) for(int i = (s); i < (n); i++) template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;} template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;} using ll = long long; using P = pair<int,int>; using Pl = pair<long long,long long>; using veci = vector<int>; using vecl = vector<long long>; using vecveci = vector<vector<int>>; using vecvecl = vector<vector<long long>>; const int MOD = 1000000007; const double pi = acos(-1); ll gcd(ll a, ll b) {if(b == 0) return a; else return gcd(b,a%b);} ll lcm(ll a, ll b) {return a*b/gcd(a,b);} template <typename T> struct BIT{ int N; vector<T> bit; BIT(int n) : N(n+1), bit(N,0) {} void add(int i, T x) { for(int idx = i; idx < N; idx += (idx & -idx)) bit[idx] += x; } T sum(int i) { T tot(0); for(int idx = i; idx > 0; idx -= (idx & -idx)) tot += bit[idx]; return tot; } T sum(int l, int r) {return sum(r) - sum(l);} int lower_bound(T w) { if(w <= 0) return 0; else { int x = 0, r = 1; while(r < N) r = r << 1; for(int len = r; len > 0; len /= 2) { if(x+len < N && bit[x+len] < w) { w -= bit[x+len]; x += len; } } return x+1; } } }; const int MAX = 100010; ll Number_of_inversions(vector<int> A) { int M = A.size(); ll tot = 0; BIT<int> seg(MAX); for(int i = 0; i < M; i++) { tot += i-seg.sum(A[i]-1); seg.add(A[i],1); } return tot; } int main() { int N; cin >> N; veci A(N); REP(i,N) cin >> A[i]; cout << Number_of_inversions(A) << endl; return 0; }