結果
問題 |
No.694 square1001 and Permutation 3
|
ユーザー |
![]() |
提出日時 | 2021-03-09 15:30:30 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 366 ms / 3,000 ms |
コード長 | 2,892 bytes |
コンパイル時間 | 1,959 ms |
コンパイル使用メモリ | 202,516 KB |
最終ジャッジ日時 | 2025-01-19 13:05:05 |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 13 |
ソースコード
#define _USE_MATH_DEFINES #include <bits/stdc++.h> using namespace std; #define FOR(i,m,n) for(int i=(m);i<(n);++i) #define REP(i,n) FOR(i,0,n) #define ALL(v) (v).begin(),(v).end() using ll = long long; constexpr int INF = 0x3f3f3f3f; constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL; constexpr double EPS = 1e-8; constexpr int MOD = 1000000007; // constexpr int MOD = 998244353; constexpr int dy[] = {1, 0, -1, 0}, dx[] = {0, -1, 0, 1}; constexpr int dy8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dx8[] = {0, -1, -1, -1, 0, 1, 1, 1}; template <typename T, typename U> inline bool chmax(T &a, U b) { return a < b ? (a = b, true) : false; } template <typename T, typename U> inline bool chmin(T &a, U b) { return a > b ? (a = b, true) : false; } struct IOSetup { IOSetup() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); std::cout << fixed << setprecision(20); } } iosetup; template <typename Abelian> struct BIT { BIT(int n, const Abelian UNITY = 0) : n(n), UNITY(UNITY), dat(n, UNITY) {} void add(int idx, Abelian val) { while (idx < n) { dat[idx] += val; idx |= idx + 1; } } Abelian sum(int idx) const { Abelian res = UNITY; --idx; while (idx >= 0) { res += dat[idx]; idx = (idx & (idx + 1)) - 1; } return res; } Abelian sum(int left, int right) const { return left < right ? sum(right) - sum(left) : UNITY; } Abelian operator[](const int idx) const { return sum(idx, idx + 1); } int lower_bound(Abelian val) const { if (val <= UNITY) return 0; int res = 0, exponent = 1; while (exponent <= n) exponent <<= 1; for (int mask = exponent >> 1; mask > 0; mask >>= 1) { if (res + mask - 1 < n && dat[res + mask - 1] < val) { val -= dat[res + mask - 1]; res += mask; } } return res; } private: int n; const Abelian UNITY; std::vector<Abelian> dat; }; template <typename T> long long inversion_number(const std::vector<T> &a) { int n = a.size(); std::vector<T> comp(a); std::sort(comp.begin(), comp.end()); comp.erase(std::unique(comp.begin(), comp.end()), comp.end()); BIT<int> bit(comp.size()); long long res = 0; for (int i = 0; i < n; ++i) { int idx = std::lower_bound(comp.begin(), comp.end(), a[i]) - comp.begin(); res += i - bit.sum(idx + 1); bit.add(idx, 1); } return res; } // https://atcoder.jp/contests/abc190/tasks/abc190_f int main() { int n; cin >> n; vector<int> a(n); REP(i, n) cin >> a[i]; vector<int> b = a; sort(ALL(b)); b.erase(unique(ALL(b)), b.end()); int m = b.size(); vector<int> cnt(m, 0); REP(i, n) { a[i] = lower_bound(ALL(b), a[i]) - b.begin(); ++cnt[a[i]]; } FOR(i, 1, m) cnt[i] += cnt[i - 1]; ll ans = inversion_number(a); REP(i, n) { cout << ans << '\n'; ans += -(a[i] > 0 ? cnt[a[i] - 1] : 0) + (n - cnt[a[i]]); } return 0; }