結果
| 問題 |
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);
| ~~~~~^~~~~~~~~~~~~~~~~
ソースコード
#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);
}