結果

問題 No.8084 ゲームブックにトライ!
ユーザー fura
提出日時 2023-09-14 00:03:50
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 54 ms / 500 ms
コード長 7,344 bytes
コンパイル時間 3,540 ms
コンパイル使用メモリ 270,848 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-07-01 08:01:30
合計ジャッジ時間 5,729 ms
ジャッジサーバーID
(参考情報)
judge5 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 1
other AC * 44
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

/*
f = {
'': 0,
'0': 1,
'00': 4,
'000': 16,
'0000': 24,
'00000': 30,
'000000': 45,
'0000000': 161,
'0000001': 91,
'00000010': 144,
'000001': 82,
'0000010': 147,
'00001': 51,
'000010': 152,
'000011': 59,
'0001': 18,
'00010': 67,
'000101': 110,
'00011': 54,
'000110': 69,
'0001101': 77,
'00011011': 157,
'000111': 81,
'0001110': 112,
'001': 10,
'0010': 12,
'00100': 15,
'001000': 75,
'0010001': 166,
'001001': 26,
'00101': 32,
'001010': 109,
'0010100': 155,
'001011': 106,
'0010111': 111,
'00101110': 127,
'0011': 14,
'00110': 89,
'001100': 105,
'001101': 93,
'0011010': 170,
'0011011': 129,
'00111': 128,
'001110': 163,
'01': 3,
'010': 20,
'0100': 23,
'01000': 76,
'010000': 126,
'0100001': 146,
'010001': 135,
'01001': 150,
'010011': 164,
'0101': 31,
'01010': 40,
'010100': 70,
'0101001': 90,
'010101': 114,
'0101011': 123,
'01010110': 138,
'01011': 47,
'010110': 61,
'0101101': 65,
'01011010': 151,
'01011011': 100,
'010110111': 158,
'011': 6,
'0110': 17,
'01100': 21,
'011000': 60,
'0110000': 72,
'0110001': 96,
'01100010': 121,
'011000101': 139,
'01100011': 107,
'011001': 33,
'0110010': 49,
'0110011': 169,
'01101': 37,
'011010': 149,
'011011': 53,
'0110111': 113,
'0111': 7,
'01110': 19,
'011100': 102,
'011101': 64,
'0111011': 98,
'01111': 116,
'011110': 133,
'011111': 132,
'1': 2,
'10': 5,
'100': 27,
'1000': 38,
'10000': 57,
'100000': 71,
'1000000': 85,
'10000001': 103,
'1000001': 145,
'10000011': 165,
'100001': 160,
'10001': 42,
'100010': 52,
'100011': 63,
'1000110': 66,
'1001': 29,
'10010': 48,
'100100': 50,
'1001000': 156,
'1001001': 119,
'10011': 92,
'100110': 101,
'1001100': 171,
'101': 8,
'1010': 22,
'10100': 34,
'101000': 87,
'1010000': 167,
'101001': 58,
'1010010': 137,
'1010011': 86,
'10101': 28,
'101010': 55,
'1010101': 79,
'10101011': 108,
'101010110': 130,
'101011': 141,
'1011': 11,
'10110': 35,
'101100': 159,
'101101': 73,
'1011010': 99,
'10110101': 115,
'10111': 13,
'101110': 84,
'101111': 97,
'1011110': 117,
'1011111': 148,
'10111110': 153,
'11': 9,
'110': 39,
'1100': 43,
'11000': 46,
'110001': 62,
'1100010': 143,
'1100011': 95,
'11001': 44,
'110010': 56,
'1100100': 124,
'11001001': 142,
'1100101': 172,
'110011': 74,
'1101': 80,
'11010': 83,
'110100': 88,
'1101000': 168,
'110101': 131,
'1101010': 154,
'11011': 104,
'110110': 118,
'1101101': 134,
'111': 25,
'1110': 41,
'11100': 125,
'111001': 162,
'11101': 68,
'111010': 120,
'1110101': 136,
'111011': 78,
'1110110': 94,
'1111': 36,
'11110': 140,
'11111': 122,
}
g = [None] * 173
for k, v in f.items():
g[v] = k
g.append(g[10])
s = ''.join(g)
while len(s) >= 8:
print(chr(int(s[:8], base=2)), end='')
s = s[8:]
# Roses are red
# Violets are blue
# Calculate and output
# the following value
# \sum_{i=1}^N \sum_{j=i+1}^N ((A_i+A_j) mod 998244353)
*/
#ifndef TEMPLATE_HPP
#define TEMPLATE_HPP
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define impl_overload4(a, b, c, d, e, ...) e
#define impl_overload5(a, b, c, d, e, f, ...) f
#define impl_overload6(a, b, c, d, e, f, g, ...) g
#define impl_overload7(a, b, c, d, e, f, g, h, ...) h
// clang-format off
#define impl_rep4(i, a, b, c) for (int i = (a); i < (b); i += (c))
#define impl_rep3(i, a, b) impl_rep4(i, a, b, 1)
#define impl_rep2(i, n) impl_rep3(i, 0, n)
#define impl_rep1(n) for (int _ = 0; _ < (n); ++_)
#define rep(...) impl_overload4(__VA_ARGS__, impl_rep4, impl_rep3, impl_rep2, impl_rep1)(__VA_ARGS__)
#define impl_rrep4(i, a, b, c) for (int i = (b) - 1; i >= (a); i -= (c))
#define impl_rrep3(i, a, b) impl_rrep4(i, a, b, 1)
#define impl_rrep2(i, n) impl_rrep3(i, 0, n)
#define rrep(...) impl_overload4(__VA_ARGS__, impl_rrep4, impl_rrep3, impl_rrep2)(__VA_ARGS__)
// clang-format on
#define all(v) std::begin(v), std::end(v)
template<typename T>
constexpr int bit(T x, unsigned int k) {
return (x >> k) & 1;
}
template<typename T>
constexpr bool chmax(T& a, const T& b) {
return a < b ? a = b, true : false;
}
template<typename T>
constexpr bool chmin(T& a, const T& b) {
return a > b ? a = b, true : false;
}
void yesno(bool b) {
std::cout << (b ? "Yes" : "No") << "\n";
}
void yes() {
yesno(true);
}
void no() {
yesno(false);
}
struct Setup {
Setup() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout << std::fixed << std::setprecision(11);
}
} setup;
#ifdef LOCAL
#include "template_local.hpp"
#else
#define show(...) ((void)0)
#endif
using uint = unsigned int;
using lint = long long;
using ulint = unsigned long long;
using namespace std;
#endif // TEMPLATE_HPP
template<class G>
class Fenwick_tree {
vector<G> a;
public:
Fenwick_tree(int n = 0) {
build(n);
}
Fenwick_tree(const vector<G>& a) {
build(a);
}
void build(int n) {
a.assign(n, G{});
}
void build(const vector<G>& a) {
this->a = a;
for (int i = 1; i <= a.size(); i++)
if (i + (i & -i) <= a.size()) (this->a)[i + (i & -i) - 1] += (this->a)[i - 1];
}
void add(int i, const G& val) {
for (i++; i <= a.size(); i += i & -i) a[i - 1] += val;
}
G sum(int l, int r) const {
if (l == 0) {
G res{};
for (; r > 0; r -= r & -r) res += a[r - 1];
return res;
}
return sum(0, r) - sum(0, l);
}
int lower_bound(G val) const {
if (!(G{} < val)) return 0;
int x = 0, k;
for (k = 1; k <= a.size(); k <<= 1)
;
for (k >>= 1; k > 0; k >>= 1)
if (x + k <= a.size() && a[x + k - 1] < val) val -= a[x + k - 1], x += k;
return x;
}
int upper_bound(G val) const {
if (val < G{}) return 0;
int x = 0, k;
for (k = 1; k <= a.size(); k <<= 1)
;
for (k >>= 1; k > 0; k >>= 1)
if (x + k <= a.size() && !(val < a[x + k - 1])) val -= a[x + k - 1], x += k;
return x;
}
};
const lint M = 998244353;
int main() {
int n;
cin >> n;
vector<lint> A(n);
rep (i, n) {
cin >> A[i];
A[i] %= M;
}
// compress coordinates
vector<lint> X = A;
sort(all(X));
X.erase(unique(all(X)), end(X));
vector<lint> P(n);
rep (i, n) {
P[i] = lower_bound(all(X), A[i]) - begin(X);
}
lint cnt = 0;
Fenwick_tree<lint> F(size(X));
rrep (i, n) {
// count j s.t. j > i and A_i + A_j >= M
int idx = lower_bound(all(X), M - A[i]) - begin(X);
cnt += F.sum(idx, size(X));
F.add(P[i], 1);
}
lint ans = (n - 1) * accumulate(all(A), 0LL);
ans -= cnt * M;
cout << ans << endl;
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0