結果
問題 | No.742 にゃんにゃんにゃん 猫の挨拶 |
ユーザー |
![]() |
提出日時 | 2020-03-17 16:55:40 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 11 ms / 2,500 ms |
コード長 | 1,368 bytes |
コンパイル時間 | 1,605 ms |
コンパイル使用メモリ | 168,148 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-30 22:46:21 |
合計ジャッジ時間 | 2,508 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 16 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;const int mod = 1e9 + 7;const int inf = (1 << 30) - 1;const ll infll = (1LL << 61) - 1;#define fast() ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)#define digit(N) cout << fixed << setprecision((N))// 1 - indexedtemplate <typename T>struct BIT{vector<T> bit;BIT(int sz) : bit(sz + 1, 0) {}// sum of [1, k]T sum(int k){T res = 0;for (int x = k; x > 0; x -= x & -x)res += bit[x];return res;}void add(int k, T w){for (int x = k; x < bit.size(); x += x & -x)bit[x] += w;}// sum of [x, y)T getSum(int x, int y){return sum(y - 1) - sum(x - 1);}// find an index i s.t. a[1] + a[2] + ⋯ + a[x] ≧ wT lower_bound(T w){if (w <= 0)return 0;T x = 0;int p = 1, N = bit.size();while (2 * p <= N)p *= 2;for (T k = p; k > 0; k /= 2){if (x + k <= N && bit[x + k] < w){w -= bit[x + k];x += k;}}return x + 1;}};using ll = long long;// p : permutationll inversion(vector<int> &p){int N = p.size();BIT<int> bit(N + 1);ll inv = 0;for (int i = 0; i < N; i++){inv += bit.getSum(p[i], N + 1);bit.add(p[i], 1);}return inv;}int main(){int N;cin >> N;vector<int> M(N);for (int i = 0; i < N; i++){cin >> M[i];}cout << inversion(M) << "\n";}