Submission #2857555
Source Code Expand
#include <bits/stdc++.h> using namespace std; using uint = unsigned int; using ll = long long; using ull = unsigned long long; constexpr ll TEN(int n) { return (n==0) ? 1 : 10*TEN(n-1); } template<class T> using V = vector<T>; template<class T> using VV = V<V<T>>; template<uint MD> struct ModInt { using M = ModInt; uint v; ModInt() : v{0} {} ModInt(ll _v) { set_v(_v % MD + MD); } M& set_v(uint _v) { v = (_v < MD) ? _v : _v - MD; return *this; } explicit operator bool() const { return v != 0; } M operator+(const M& r) const { return M().set_v(v + r.v); } M operator-(const M& r) const { return M().set_v(v + MD - r.v); } M operator*(const M& r) const { return M().set_v(ull(v) * r.v % MD); } M operator/(const M& r) const { return *this * r.inv(); } M& operator+=(const M& r) { return *this = *this + r; } M& operator-=(const M& r) { return *this = *this - r; } M& operator*=(const M& r) { return *this = *this * r; } M& operator/=(const M& r) { return *this = *this / r; } M pow(ll n) const { M x = *this, r = 1; while (n) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; } M inv() const { return (*this).pow(MD - 2); } }; using Mint = ModInt<TEN(9)+7>; template<class T> struct Fenwick { int n; V<T> seg; Fenwick() {} Fenwick(int _n) : n(_n) { seg = V<T>(n + 1, T(0)); } /// i番目の要素にxを追加する void add(int i, T x) { i++; while (i <= n) { seg[i] += x; i += i & -i; } } /// [0, i)のsum T sum(int i) { T s{0}; while (i > 0) { s += seg[i]; i -= i & -i; } return s; } /// [a, b)のsum T sum(int a, int b) { return sum(b) - sum(a); } }; int main() { cin.tie(0); ios::sync_with_stdio(false); cout << setprecision(20); int n; cin >> n; V<int> h(n), cnt(n); for (int i = 0; i < n; i++) { cin >> h[i]; h[i]--; cnt[h[i]]++; } for (int i = n-2; i >= 0; i--) { cnt[i] += cnt[i+1]; } for (int i = 0; i < n; i++) { cnt[i] -= (n-1-i); if (cnt[i] <= 0) { cout << 0 << endl; return 0; } } V<Mint> freq(n); freq[0] = Mint(1); for (int i = 1; i < n; i++) { freq[i] = freq[i-1]; if (cnt[i] > 1) freq[i] *= Mint(cnt[i]-1) / Mint(cnt[i]); } V<int> idx(n); iota(idx.begin(), idx.end(), 0); sort(idx.begin(), idx.end(), [&](int a, int b){ return tie(h[a], a) < tie(h[b], b); }); Fenwick<Mint> fw(n); Mint sml = 0, smr = 0; int up = n-1; V<int> div_p; for (int i = 0; i < n; i++) if (cnt[i] == 1) div_p.push_back(i); for (int i = n-1; i >= 0; i--) { int p = idx[i]; while (div_p.size() && h[p] < div_p.back()) { int le = div_p.back(); div_p.pop_back(); while (le <= h[idx[up]]) { assert(i < up); int p2 = idx[up]; Mint f2 = freq[h[p2]]; fw.add(p2, Mint(0) - f2); up--; } } Mint f = freq[h[p]]; smr += fw.sum(p+1, n) / f; sml += fw.sum(0, p) / f; fw.add(p, f); } Mint sm = (smr - sml) / Mint(2); { Fenwick<Mint> fw_inv(n); for (int d: h) { sm += fw_inv.sum(d+1, n); fw_inv.add(d, 1); } } for (int i = 0; i < n; i++) { sm *= cnt[i]; } cout << sm.v << endl; // cout << sml.v << " " << smr.v << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | E - Inversions |
User | yosupo |
Language | C++14 (GCC 5.4.1) |
Score | 1700 |
Code Size | 3806 Byte |
Status | AC |
Exec Time | 157 ms |
Memory | 5876 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 1700 / 1700 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt |
All | sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt, subtask_1_29.txt, subtask_1_30.txt, subtask_1_31.txt, subtask_1_32.txt, subtask_1_33.txt, subtask_1_34.txt, subtask_1_35.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample_01.txt | AC | 1 ms | 256 KB |
sample_02.txt | AC | 1 ms | 256 KB |
sample_03.txt | AC | 1 ms | 256 KB |
sample_04.txt | AC | 1 ms | 256 KB |
subtask_1_01.txt | AC | 1 ms | 256 KB |
subtask_1_02.txt | AC | 1 ms | 256 KB |
subtask_1_03.txt | AC | 13 ms | 1280 KB |
subtask_1_04.txt | AC | 2 ms | 384 KB |
subtask_1_05.txt | AC | 34 ms | 1408 KB |
subtask_1_06.txt | AC | 96 ms | 3968 KB |
subtask_1_07.txt | AC | 37 ms | 1664 KB |
subtask_1_08.txt | AC | 45 ms | 2428 KB |
subtask_1_09.txt | AC | 45 ms | 2808 KB |
subtask_1_10.txt | AC | 17 ms | 1280 KB |
subtask_1_11.txt | AC | 88 ms | 2944 KB |
subtask_1_12.txt | AC | 92 ms | 3072 KB |
subtask_1_13.txt | AC | 120 ms | 4856 KB |
subtask_1_14.txt | AC | 20 ms | 1792 KB |
subtask_1_15.txt | AC | 19 ms | 1792 KB |
subtask_1_16.txt | AC | 149 ms | 4992 KB |
subtask_1_17.txt | AC | 123 ms | 4992 KB |
subtask_1_18.txt | AC | 123 ms | 4992 KB |
subtask_1_19.txt | AC | 129 ms | 5876 KB |
subtask_1_20.txt | AC | 103 ms | 5876 KB |
subtask_1_21.txt | AC | 101 ms | 5876 KB |
subtask_1_22.txt | AC | 157 ms | 4992 KB |
subtask_1_23.txt | AC | 157 ms | 4992 KB |
subtask_1_24.txt | AC | 150 ms | 5372 KB |
subtask_1_25.txt | AC | 20 ms | 1792 KB |
subtask_1_26.txt | AC | 19 ms | 1792 KB |
subtask_1_27.txt | AC | 149 ms | 4992 KB |
subtask_1_28.txt | AC | 123 ms | 4992 KB |
subtask_1_29.txt | AC | 124 ms | 4992 KB |
subtask_1_30.txt | AC | 130 ms | 5876 KB |
subtask_1_31.txt | AC | 102 ms | 5876 KB |
subtask_1_32.txt | AC | 101 ms | 5876 KB |
subtask_1_33.txt | AC | 152 ms | 4992 KB |
subtask_1_34.txt | AC | 157 ms | 4992 KB |
subtask_1_35.txt | AC | 145 ms | 5496 KB |