結果

問題 No.1300 Sum of Inversions
ユーザー Ricky_pon
提出日時 2020-11-27 21:54:07
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 167 ms / 2,000 ms
コード長 4,820 bytes
コンパイル時間 2,536 ms
コンパイル使用メモリ 208,576 KB
最終ジャッジ日時 2025-01-16 07:03:34
ジャッジサーバーID
(参考情報)
judge5 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 34
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:165:19: warning: format ‘%lld’ expects argument of type ‘long long int*’, but argument 2 has type ‘modint<998244353>::i64*’ {aka ‘long int*’} [-Wformat=]
  165 |         scanf("%lld", &a[i].a);
      |                ~~~^   ~~~~~~~
      |                   |   |
      |                   |   modint<998244353>::i64* {aka long int*}
      |                   long long int*
      |                %ld
main.cpp:192:16: warning: format ‘%lld’ expects argument of type ‘long long int’, but argument 2 has type ‘modint<998244353>::i64’ {aka ‘long int’} [-Wformat=]
  192 |     printf("%lld\n", ans.a);
      |             ~~~^     ~~~~~
      |                |         |
      |                |         modint<998244353>::i64 {aka long int}
      |                long long int
      |             %ld
main.cpp:162:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  162 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
main.cpp:165:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  165 |         scanf("%lld", &a[i].a);
      |         ~~~~~^~~~~~~~~~~~~~~~~

ソースコード

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