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
AC × 4
AC × 43
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