結果

問題 No.694 square1001 and Permutation 3
ユーザー oshibori
提出日時 2018-06-09 01:08:07
言語 C++14
(gcc 13.3.0 + boost 1.87.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
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 1
other AC * 13
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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) {
// i0ibit使
//
T ret(0);
for (int j = i; j > 0; j -= j & (-j))
ret += d[j];
return ret;
}
void add(int i, T x) {
// inibit使
//
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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0