結果
問題 | No.1300 Sum of Inversions |
ユーザー | AC2K |
提出日時 | 2024-01-22 11:55:13 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 12,847 bytes |
コンパイル時間 | 3,263 ms |
コンパイル使用メモリ | 259,076 KB |
実行使用メモリ | 7,912 KB |
最終ジャッジ日時 | 2024-09-28 06:22:41 |
合計ジャッジ時間 | 8,736 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 83 ms
6,948 KB |
testcase_04 | AC | 80 ms
6,772 KB |
testcase_05 | AC | 66 ms
6,036 KB |
testcase_06 | AC | 93 ms
7,416 KB |
testcase_07 | AC | 91 ms
7,012 KB |
testcase_08 | AC | 102 ms
7,528 KB |
testcase_09 | AC | 98 ms
7,380 KB |
testcase_10 | AC | 53 ms
5,500 KB |
testcase_11 | AC | 53 ms
5,560 KB |
testcase_12 | AC | 87 ms
6,912 KB |
testcase_13 | AC | 81 ms
6,604 KB |
testcase_14 | AC | 108 ms
7,892 KB |
testcase_15 | AC | 103 ms
7,240 KB |
testcase_16 | AC | 84 ms
6,816 KB |
testcase_17 | AC | 52 ms
5,476 KB |
testcase_18 | AC | 63 ms
5,960 KB |
testcase_19 | AC | 71 ms
6,264 KB |
testcase_20 | AC | 77 ms
6,436 KB |
testcase_21 | AC | 72 ms
6,944 KB |
testcase_22 | AC | 67 ms
6,940 KB |
testcase_23 | AC | 93 ms
7,256 KB |
testcase_24 | AC | 69 ms
6,940 KB |
testcase_25 | AC | 57 ms
6,944 KB |
testcase_26 | AC | 56 ms
6,944 KB |
testcase_27 | AC | 65 ms
6,940 KB |
testcase_28 | AC | 106 ms
7,464 KB |
testcase_29 | AC | 70 ms
6,944 KB |
testcase_30 | AC | 100 ms
7,380 KB |
testcase_31 | AC | 65 ms
6,944 KB |
testcase_32 | AC | 70 ms
6,940 KB |
testcase_33 | AC | 60 ms
7,912 KB |
testcase_34 | AC | 66 ms
7,816 KB |
testcase_35 | AC | 69 ms
7,808 KB |
testcase_36 | WA | - |
ソースコード
#line 1 "Library/src/debug.hpp" #ifdef ONLINE_JUDGE #define debug(x) void(0) #else #define _GLIBCXX_DEBUG #define debug(x) std::cerr << __LINE__ << " : " << #x << " = " << (x) << std::endl #endif #line 2 "Library/src/stream.hpp" #include <ctype.h> #include <stdio.h> #include <string> #line 2 "Library/src/internal/type_traits.hpp" #include <iostream> #include <limits> #include <numeric> #include <typeinfo> #include <cstdint> namespace kyopro { namespace internal { template <typename... Args> struct first_enabled {}; template <typename T, typename... Args> struct first_enabled<std::enable_if<true, T>, Args...> { using type = T; }; template <typename T, typename... Args> struct first_enabled<std::enable_if<false, T>, Args...> : first_enabled<Args...> {}; template <typename T, typename... Args> struct first_enabled<T, Args...> { using type = T; }; template <typename... Args> using first_enabled_t = typename first_enabled<Args...>::type; template <int dgt, std::enable_if_t<dgt <= 128>* = nullptr> struct int_least { using type = first_enabled_t<std::enable_if<dgt <= 8, std::int8_t>, std::enable_if<dgt <= 16, std::int16_t>, std::enable_if<dgt <= 32, std::int32_t>, std::enable_if<dgt <= 64, std::int64_t>, std::enable_if<dgt <= 128, __int128_t>>; }; template <int dgt, std::enable_if_t<dgt <= 128>* = nullptr> struct uint_least { using type = first_enabled_t<std::enable_if<dgt <= 8, std::uint8_t>, std::enable_if<dgt <= 16, std::uint16_t>, std::enable_if<dgt <= 32, std::uint32_t>, std::enable_if<dgt <= 64, std::uint64_t>, std::enable_if<dgt <= 128, __uint128_t>>; }; template <int dgt> using int_least_t = typename int_least<dgt>::type; template <int dgt> using uint_least_t = typename uint_least<dgt>::type; template <typename T> using double_size_uint_t = uint_least_t<2 * std::numeric_limits<T>::digits>; template <typename T> using double_size_int_t = int_least_t<2 * std::numeric_limits<T>::digits>; struct modint_base {}; template <typename T> using is_modint = std::is_base_of<modint_base, T>; template <typename T> using is_modint_t = std::enable_if_t<is_modint<T>::value>; // is_integral template <typename T> using is_integral_t = std::enable_if_t<std::is_integral_v<T> || std::is_same_v<T, __int128_t> || std::is_same_v<T, __uint128_t>>; }; // namespace internal }; // namespace kyopro /* * @ref https://qiita.com/kazatsuyu/items/f8c3b304e7f8b35263d8 */ #line 6 "Library/src/stream.hpp" namespace kyopro { inline void single_read(char& c) { c = getchar_unlocked(); while (isspace(c)) c = getchar_unlocked(); } template <typename T, internal::is_integral_t<T>* = nullptr> inline void single_read(T& a) { a = 0; bool is_negative = false; char c = getchar_unlocked(); while (isspace(c)) { c = getchar_unlocked(); } if (c == '-') is_negative = true, c = getchar_unlocked(); while (isdigit(c)) { a = 10 * a + (c - '0'); c = getchar_unlocked(); } if (is_negative) a *= -1; } template <typename T, internal::is_modint_t<T>* = nullptr> inline void single_read(T& a) { long long x; single_read(x); a = T(x); } inline void single_read(std::string& str) noexcept { char c = getchar_unlocked(); while (isspace(c)) c = getchar_unlocked(); while (!isspace(c)) { str += c; c = getchar_unlocked(); } } template<typename T> inline void read(T& x) noexcept {single_read(x);} template <typename Head, typename... Tail> inline void read(Head& head, Tail&... tail) noexcept { single_read(head), read(tail...); } inline void single_write(char c) noexcept { putchar_unlocked(c); } template <typename T, internal::is_integral_t<T>* = nullptr> inline void single_write(T a) noexcept { if (!a) { putchar_unlocked('0'); return; } if constexpr (std::is_signed_v<T>) { if (a < 0) putchar_unlocked('-'), a *= -1; } constexpr int d = std::numeric_limits<T>::digits10; char s[d + 1]; int now = d + 1; while (a) { s[--now] = (char)'0' + a % 10; a /= 10; } while (now <= d) putchar_unlocked(s[now++]); } template <typename T, internal::is_modint_t<T>* = nullptr> inline void single_write(T a) noexcept { single_write(a.val()); } inline void single_write(const std::string& str) noexcept { for (auto c : str) { putchar_unlocked(c); } } template <typename T> inline void write(T x) noexcept { single_write(x); } template <typename Head, typename... Tail> inline void write(Head head, Tail... tail) noexcept { single_write(head); putchar_unlocked(' '); write(tail...); } template <typename... Args> inline void put(Args... x) noexcept { write(x...); putchar_unlocked('\n'); } }; // namespace kyopro /** * @brief 高速入出力 */ #line 2 "Library/src/template.hpp" #include <bits/stdc++.h> #define rep(i, n) for (int i = 0; i < (n); i++) #define all(x) std::begin(x), std::end(x) #define popcount(x) __builtin_popcountll(x) using i128 = __int128_t; using ll = long long; using ld = long double; using graph = std::vector<std::vector<int>>; using P = std::pair<int, int>; constexpr int inf = std::numeric_limits<int>::max() / 2; constexpr ll infl = std::numeric_limits<ll>::max() / 2; const long double pi = acosl(-1); constexpr uint64_t MOD = 1e9 + 7; constexpr uint64_t MOD2 = 998244353; constexpr int dx[] = {1, 0, -1, 0, 1, -1, -1, 1, 0}; constexpr int dy[] = {0, 1, 0, -1, 1, 1, -1, -1, 0}; template <typename T1, typename T2> constexpr inline bool chmax(T1& a, T2 b) { return a < b && (a = b, true); } template <typename T1, typename T2> constexpr inline bool chmin(T1& a, T2 b) { return a > b && (a = b, true); } #line 4 "a.cpp" #line 3 "Library/src/data-structure/BIT.hpp" namespace kyopro { template <typename T> class BIT { std::vector<T> bit; int n; public: BIT() : BIT(0) {} BIT(int n) : n(n), bit(n + 1, T()) {} void add(int p, T w) { p++; for (int x = p; x <= n; x += x & -x) { bit[x] += w; } } T sum(int p) const { T s = 0; for (int x = p; x > 0; x -= x & -x) { s += bit[x]; } return s; } T sum(int l, int r) const { return sum(r) - sum(l); } int lower_bound(T w) const { if (w <= 0) return 0; int x = 0; int k = 1; while (k < n) k <<= 1; for (; k > 0; k >>= 1) { if (x + k <= n && bit[x + k] < w) { w -= bit[x + k]; x += k; } } return x + 1; } T operator[](int i) { return sum(i + 1) - sum(i); } void update(int i, T v) { add(i, -sum(i + 1) + sum(i) + v); } }; }; // namespace kyopro /** * @brief Binary Index Tree */ #line 5 "Library/src/math/static_modint.hpp" #line 4 "Library/src/math/gcd.hpp" namespace kyopro { template <typename T> constexpr inline T _gcd(T a, T b) noexcept { assert(a >= 0 && b >= 0); if (a == 0 || b == 0) return a + b; int d = std::min<T>(__builtin_ctzll(a), __builtin_ctzll(b)); a >>= __builtin_ctzll(a), b >>= __builtin_ctzll(b); while (a != b) { if (!a || !b) { return a + b; } if (a >= b) { a -= b; a >>= __builtin_ctzll(a); } else { b -= a; b >>= __builtin_ctzll(b); } } return a << d; } template <typename T> constexpr inline T ext_gcd(T a, T b, T& x, T& y) noexcept { x = 1, y = 0; T nx = 0, ny = 1; while (b) { T q = a / b; std::tie(a, b) = std::pair<T, T>{b, a % b}; std::tie(x, nx) = std::pair<T, T>{nx, x - nx * q}; std::tie(y, ny) = std::pair<T, T>{ny, y - ny * q}; } return a; } }; // namespace kyopro #line 8 "Library/src/math/static_modint.hpp" namespace kyopro { template <int _mod, std::enable_if_t<_mod >= 0>* = nullptr> class modint : internal::modint_base { using mint = modint<_mod>; using i32 = std::int32_t; using u32 = std::uint32_t; using i64 = std::int64_t; using u64 = std::uint64_t; u32 v; constexpr u32 normalize(i64 v_) const noexcept { v_ %= _mod; if (v_ < 0) { v_ += _mod; } return v_; } public: static constexpr u32 mod() noexcept { return _mod; } constexpr modint() noexcept : v(0) {} constexpr modint(i64 v_) noexcept : v(normalize(v_)) {} static mint raw(u32 a) { mint m; m.v = a; return m; } constexpr u32 val() const noexcept { return v; } constexpr mint& operator+=(const mint& rhs) noexcept { v += rhs.val(); if (v >= _mod) { v -= _mod; } return (*this); } constexpr mint& operator-=(const mint& rhs) noexcept { v += _mod - rhs.val(); if (v >= _mod) { v -= _mod; } return (*this); } constexpr mint& operator*=(const mint& rhs) noexcept { v = (u64)v * rhs.val() % _mod; return (*this); } constexpr mint operator+(const mint& r) const noexcept { return mint(*this) += r; } constexpr mint operator-(const mint& r) const noexcept { return mint(*this) -= r; } constexpr mint operator*(const mint& r) const noexcept { return mint(*this) *= r; } constexpr mint& operator+=(i64 rhs) noexcept { (*this) += mint(rhs); return (*this); } constexpr mint& operator-=(i64 rhs) noexcept { (*this) -= mint(rhs); return (*this); } constexpr mint& operator*=(i64 rhs) noexcept { (*this) *= mint(rhs); return (*this); } constexpr friend mint operator+(i64 l, const mint& r) noexcept { return mint(l) += r; } constexpr friend mint operator-(i64 l, const mint& r) noexcept { return mint(l) -= r; } constexpr friend mint operator*(i64 l, const mint& r) noexcept { return mint(l) *= r; } constexpr mint operator+(i64 r) const noexcept { return mint(*this) += r; } constexpr mint operator-(i64 r) const noexcept { return mint(*this) -= r; } constexpr mint operator*(i64 r) const noexcept { return mint(*this) *= r; } constexpr mint& operator=(i64 r) noexcept { return (*this) = mint(r); } constexpr bool operator==(const mint& r) const noexcept { return (*this).val() == r.val(); } template <typename T, internal::is_integral_t<T>* = nullptr> constexpr mint pow(T e) const noexcept { mint ans(1), base(*this); while (e) { if (e & 1) { ans *= base; } base *= base; e >>= 1; } return ans; } constexpr mint inv() const noexcept { long long x, y; auto d = ext_gcd((long long)_mod, (long long)v, x, y); assert(d == 1); return mint(y); } constexpr mint& operator/=(const mint& r) noexcept { return (*this) *= r.inv(); } constexpr mint operator/(const mint& r) const noexcept { return mint(*this) *= r.inv(); } constexpr friend mint operator/(const mint& l, i64 r) noexcept { return mint(l) /= mint(r); } constexpr friend mint operator/(i64 l, const mint& r) noexcept { return mint(l) /= mint(r); } }; }; // namespace kyopro /** * @brief static modint */ #line 7 "a.cpp" using namespace std; using namespace kyopro; using mint = modint<998244353>; int main() { int n; read(n); vector<int> a(n); rep(i, n) read(a[i]); vector<int> pressed(n); { vector va = a; sort(all(va)); va.erase(unique(all(va)), va.end()); rep(i, n) pressed[i] = lower_bound(all(va), a[i]) - va.begin(); } vector<mint> cnt_ij(n), sum_ij(n); { BIT<mint> cnt_fw(n), sum_fw(n); rep(i, n) { cnt_ij[i] = cnt_fw.sum(pressed[i] + 1, n); sum_ij[i] = a[i] * cnt_fw.sum(pressed[i] + 1, n) + sum_fw.sum(pressed[i] + 1, n); cnt_fw.add(pressed[i], mint::raw(1)); sum_fw.add(pressed[i], mint::raw(a[i])); } } // rep(i, n) put(cnt_ij[i], sum_ij[i]); mint ans = 0; { BIT<mint> cnt_fw(n), sum_fw(n); rep(i, n) { ans += mint(a[i]) * cnt_fw.sum(pressed[i] + 1, n) + sum_fw.sum(pressed[i] + 1, n); cnt_fw.add(pressed[i], cnt_ij[i]); sum_fw.add(pressed[i], sum_ij[i]); } } put(ans); }