結果
問題 | No.694 square1001 and Permutation 3 |
ユーザー | oshibori |
提出日時 | 2018-06-09 01:08:07 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,155 ms / 3,000 ms |
コード長 | 3,561 bytes |
コンパイル時間 | 1,874 ms |
コンパイル使用メモリ | 178,096 KB |
実行使用メモリ | 34,488 KB |
最終ジャッジ日時 | 2024-06-30 12:12:05 |
合計ジャッジ時間 | 10,312 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,940 KB |
testcase_02 | AC | 2 ms
6,940 KB |
testcase_03 | AC | 2 ms
6,940 KB |
testcase_04 | AC | 3 ms
6,940 KB |
testcase_05 | AC | 3 ms
6,940 KB |
testcase_06 | AC | 2 ms
6,944 KB |
testcase_07 | AC | 835 ms
34,368 KB |
testcase_08 | AC | 988 ms
34,440 KB |
testcase_09 | AC | 1,110 ms
34,404 KB |
testcase_10 | AC | 806 ms
34,480 KB |
testcase_11 | AC | 1,131 ms
34,404 KB |
testcase_12 | AC | 1,155 ms
34,488 KB |
testcase_13 | AC | 2 ms
6,944 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; #ifdef _DEBUG #define _GLIBCXX_DEBUG #include "dump.hpp" #else #define dump(...) #endif #define int long long // typedef __int128_t Int; #define DBG 1 #define rep(i, a, b) for (int i = (a); i < (b); i++) #define rrep(i, a, b) for (int i = (b)-1; i >= (a); i--) #define loop(n) rep(loop, (0), (n)) #define all(c) begin(c), end(c) const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f; const int MOD = (int)(1e9) + 7; const double PI = acos(-1); const double EPS = 1e-9; template <class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; } template <class T> bool chmin(T &a, const T &b) { if (a > b) { a = b; return true; } return false; } template <typename T> struct BinaryIndexedTree { // 1-indexed int n; vector<T> d; // d[x] が管理する区間の長さは,x の最も下の立っているビット(x&-x) BinaryIndexedTree(int m) : n(m) { // 0 以外の値で初期化をするとき // ・add を 𝑁 回呼び出せば 𝑂(𝑁 log 𝑁) // ・𝑣𝑥 = 1 で初期化するなら bit[x] = x & -x; (x&-x は区間の長さ) // ・一般には bit[x] を 𝑣𝑥 で初期化したのち // for (int x = 1; x < N; ++x) bit[x + (x & -x)] += bit[x]; d.assign(m + 1, 0); } T sum(int a, int b) { return sum(b) - sum(a - 1); } T sum(int i) { // iから0にiの最も下の立っているbitを使って到達する最短距離 // 次に足すべき区間は,番号から区間の長さを引くと求まる T ret(0); for (int j = i; j > 0; j -= j & (-j)) ret += d[j]; return ret; } void add(int i, T x) { // iからnにiの最も下の立っているbitを使って到達する最短距離 // 次に更新すべき区間は,番号に区間の長さを足すと求まる for (int j = i; j <= n; j += j & (-j)) d[j] += x; } int lower_bound(T w) { // 二分木の分かれ方に従って二分探索する // 左の子に進むか右の子に進むかを知るためには,左の子の範囲の和がわかればよい // (index/2) // ちょうど BIT がもっている情報,𝑂(1) 時間で得られる // if (w <= 0) return 0; int x(0), y; for (y = 1; 2 * y <= n; y <<= 1) ; for (int k = y; k > 0; k >>= 1) { if (x + k <= n && d[x + k] < w) { w -= d[x + k]; x += k; } } return x + 1; } }; template <typename T> vector<T> compress(vector<T> &a) { // 座標圧縮 vector<T> ret; ret.insert(ret.end(), all(a)); sort(all(ret)); ret.erase(unique(all(ret)), ret.end()); rep(i, 0, a.size()) a[i] = distance(ret.begin(), lower_bound(all(ret), a[i])); return ret; } int theNunberOfInversion(vector<int> &a) { compress(a); BinaryIndexedTree<int> bit(a.size()); int ans(0); rep(i, 0, a.size()) { ans += i - bit.sum(a[i]); bit.add(a[i], 1); } return ans; } signed main() { cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(12); int N; cin >> N; vector<int> A(N); rep(i, 0, N) { cin >> A[i]; } rep(i, 0, N) A.push_back(A[i]); vector<int> v(2 * N); BinaryIndexedTree<int> bit(2 * N); compress(A); int ans = 0; rep(i, 0, N) { ans += i - bit.sum(A[i] + 1); bit.add(A[i] + 1, 1); } rep(i, 0, N) { cout<<ans<<endl; bit.add(A[i]+1,-1); ans-=bit.sum(A[i]); ans+=bit.sum(A[i]+2,N); bit.add(A[i]+1,1); } return 0; }