結果

問題 No.1300 Sum of Inversions
ユーザー Ricky_ponRicky_pon
提出日時 2020-11-27 21:54:07
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 158 ms / 2,000 ms
コード長 4,820 bytes
コンパイル時間 2,478 ms
コンパイル使用メモリ 214,628 KB
実行使用メモリ 14,848 KB
最終ジャッジ日時 2023-10-01 05:30:19
合計ジャッジ時間 7,927 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 118 ms
12,252 KB
testcase_04 AC 114 ms
11,864 KB
testcase_05 AC 90 ms
10,692 KB
testcase_06 AC 130 ms
13,380 KB
testcase_07 AC 126 ms
12,720 KB
testcase_08 AC 144 ms
13,976 KB
testcase_09 AC 139 ms
13,632 KB
testcase_10 AC 74 ms
9,400 KB
testcase_11 AC 75 ms
9,672 KB
testcase_12 AC 117 ms
12,104 KB
testcase_13 AC 116 ms
11,828 KB
testcase_14 AC 158 ms
14,572 KB
testcase_15 AC 143 ms
13,628 KB
testcase_16 AC 117 ms
12,472 KB
testcase_17 AC 71 ms
9,228 KB
testcase_18 AC 83 ms
10,088 KB
testcase_19 AC 100 ms
11,024 KB
testcase_20 AC 105 ms
11,188 KB
testcase_21 AC 101 ms
11,252 KB
testcase_22 AC 92 ms
10,448 KB
testcase_23 AC 133 ms
13,372 KB
testcase_24 AC 96 ms
10,696 KB
testcase_25 AC 80 ms
9,792 KB
testcase_26 AC 78 ms
9,652 KB
testcase_27 AC 87 ms
10,420 KB
testcase_28 AC 149 ms
14,120 KB
testcase_29 AC 101 ms
11,300 KB
testcase_30 AC 141 ms
13,976 KB
testcase_31 AC 93 ms
10,744 KB
testcase_32 AC 97 ms
11,016 KB
testcase_33 AC 74 ms
14,848 KB
testcase_34 AC 89 ms
14,848 KB
testcase_35 AC 88 ms
14,724 KB
testcase_36 AC 93 ms
14,788 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

//#include <atcoder/all>
#define For(i, a, b) for (int(i) = (int)(a); (i) < (int)(b); ++(i))
#define rFor(i, a, b) for (int(i) = (int)(a)-1; (i) >= (int)(b); --(i))
#define rep(i, n) For((i), 0, (n))
#define rrep(i, n) rFor((i), (n), 0)
#define fi first
#define se second
using namespace std;
typedef long long lint;
typedef unsigned long long ulint;
typedef pair<int, int> pii;
typedef pair<lint, lint> pll;
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 <class T>
T div_floor(T a, T b) {
    if (b < 0) a *= -1, b *= -1;
    return a >= 0 ? a / b : (a + 1) / b - 1;
}
template <class T>
T div_ceil(T a, T b) {
    if (b < 0) a *= -1, b *= -1;
    return a > 0 ? (a - 1) / b + 1 : a / b;
}

constexpr lint mod = 1000000007;
constexpr lint INF = mod * mod;
constexpr int MAX = 100010;

template <int_fast64_t MOD>
struct modint {
    using i64 = int_fast64_t;
    i64 a;
    modint(const i64 a_ = 0) : a(a_) {
        if (a > MOD)
            a %= MOD;
        else if (a < 0)
            (a %= MOD) += MOD;
    }
    modint inv() {
        i64 t = 1, n = MOD - 2, x = a;
        while (n) {
            if (n & 1) (t *= x) %= MOD;
            (x *= x) %= MOD;
            n >>= 1;
        }
        modint ret(t);
        return ret;
    }
    bool operator==(const modint x) const { return a == x.a; }
    bool operator!=(const modint x) const { return a != x.a; }
    modint operator+(const modint x) const { return modint(*this) += x; }
    modint operator-(const modint x) const { return modint(*this) -= x; }
    modint operator*(const modint x) const { return modint(*this) *= x; }
    modint operator/(const modint x) const { return modint(*this) /= x; }
    modint operator^(const lint x) const { return modint(*this) ^= x; }
    modint &operator+=(const modint &x) {
        a += x.a;
        if (a >= MOD) a -= MOD;
        return *this;
    }
    modint &operator-=(const modint &x) {
        a -= x.a;
        if (a < 0) a += MOD;
        return *this;
    }
    modint &operator*=(const modint &x) {
        (a *= x.a) %= MOD;
        return *this;
    }
    modint &operator/=(modint x) {
        (a *= x.inv().a) %= MOD;
        return *this;
    }
    modint &operator^=(lint n) {
        i64 ret = 1;
        while (n) {
            if (n & 1) (ret *= a) %= MOD;
            (a *= a) %= MOD;
            n >>= 1;
        }
        a = ret;
        return *this;
    }
    modint operator-() const { return modint(0) - *this; }
    modint &operator++() { return *this += 1; }
    modint &operator--() { return *this -= 1; }
    bool operator<(const modint x) const { return a < x.a; }
};

using mint = modint<998244353>;

vector<mint> fact;
vector<mint> revfact;

void setfact(int n) {
    fact.resize(n + 1);
    revfact.resize(n + 1);
    fact[0] = 1;
    rep(i, n) fact[i + 1] = fact[i] * mint(i + 1);

    revfact[n] = fact[n].inv();
    for (int i = n - 1; i >= 0; i--) revfact[i] = revfact[i + 1] * mint(i + 1);
}

mint getC(int n, int r) {
    if (n < r) return 0;
    return fact[n] * revfact[r] * revfact[n - r];
}

mint f(int n) { return mint(n) * mint(n - 1) / mint(2); }

template <typename T>
struct BinaryIndexedTree {
    vector<T> node;

    BinaryIndexedTree(int n) { node.resize(n + 1, {}); }

    void update(int i, T x) {
        ++i;
        while (i < (int)node.size()) {
            node[i] += x;
            i += (i & -i);
        }
    }

    T query(int i) {
        ++i;
        T ret = 0;
        while (i) {
            ret += node[i];
            i -= (i & -i);
        }
        return ret;
    }

    T query(int l, int r) { return query(r - 1) - query(l - 1); }
};

vector<int> v;

int get_idx(int x) { return lower_bound(v.begin(), v.end(), x) - v.begin(); }

int main() {
    int n;
    scanf("%d", &n);
    mint a[n];
    rep(i, n) {
        scanf("%lld", &a[i].a);
        v.push_back(a[i].a);
    }
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());

    int L[n], R[n];
    mint vl[n], vr[n];
    BinaryIndexedTree<int> btl(n), btr(n);
    BinaryIndexedTree<mint> bvl(n), bvr(n);
    rep(i, n) {
        int idx = get_idx(a[i].a);
        L[i] = btl.query(idx + 1, n);
        vl[i] = bvl.query(idx + 1, n);
        btl.update(idx, 1);
        bvl.update(idx, a[i]);
    }
    rrep(i, n) {
        int idx = get_idx(a[i].a);
        R[i] = btr.query(0, idx);
        vr[i] = bvr.query(0, idx);
        btr.update(idx, 1);
        bvr.update(idx, a[i]);
    }

    mint ans = 0;
    rep(i, n) { ans += a[i] * 1LL * L[i] * R[i] + vl[i] * R[i] + vr[i] * L[i]; }
    printf("%lld\n", ans.a);
}
0