#1021062 (C++17) No.2941 Sigma Music Game Score Problem

提出ソース

結果

問題	No.2941 Sigma Music Game Score Problem
ユーザー	wai4u
提出日時	2024-10-19 01:23:07
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	221 ms / 2,500 ms
コード長	12,911 bytes
コンパイル時間	3,660 ms
コンパイル使用メモリ	224,156 KB
実行使用メモリ	11,036 KB
最終ジャッジ日時	2024-10-19 01:23:15
合計ジャッジ時間	7,672 ms
ジャッジサーバーID （参考情報）	judge2 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	2 ms 6,816 KB
testcase_02	AC	2 ms 6,816 KB
testcase_03	AC	2 ms 6,820 KB
testcase_04	AC	2 ms 6,824 KB
testcase_05	AC	2 ms 6,820 KB
testcase_06	AC	2 ms 6,820 KB
testcase_07	AC	2 ms 6,816 KB
testcase_08	AC	2 ms 6,816 KB
testcase_09	AC	3 ms 6,820 KB
testcase_10	AC	2 ms 6,816 KB
testcase_11	AC	2 ms 6,820 KB
testcase_12	AC	2 ms 6,820 KB
testcase_13	AC	3 ms 6,820 KB
testcase_14	AC	4 ms 6,816 KB
testcase_15	AC	2 ms 6,820 KB
testcase_16	AC	156 ms 8,960 KB
testcase_17	AC	175 ms 9,400 KB
testcase_18	AC	201 ms 10,752 KB
testcase_19	AC	159 ms 8,940 KB
testcase_20	AC	135 ms 7,924 KB
testcase_21	AC	59 ms 6,820 KB
testcase_22	AC	64 ms 6,816 KB
testcase_23	AC	59 ms 6,820 KB
testcase_24	AC	206 ms 10,860 KB
testcase_25	AC	25 ms 6,816 KB
testcase_26	AC	2 ms 6,820 KB
testcase_27	AC	2 ms 6,820 KB
testcase_28	AC	2 ms 6,820 KB
testcase_29	AC	60 ms 6,824 KB
testcase_30	AC	94 ms 8,168 KB
testcase_31	AC	218 ms 11,036 KB
testcase_32	AC	221 ms 11,032 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
#include <iostream>
#include <map>
#include <set>
using namespace std;
using ll = long long;
using u32 = unsigned int;
using u64 = unsigned long long;
using i128 = __int128;
using u128 = unsigned __int128;
#include <bits/stdc++.h>
using namespace std;
using f128 = _Float128;
using dbl = double;
using ld = long double;
#include <tuple>
using std::tuple;
template <class... T>
using tup = tuple<T...>;
#include <vector>
using std::vector;
template <class T>
using vc = vector<T>;
template <class T>
using vvc = vc<vc<T>>;
template <class T>
using vvvc = vc<vvc<T>>;
template <class T>
using vvvvc = vc<vvvc<T>>;
#define VC(T, a, ...) auto a = vector<T>(__VA_ARGS__)
#define VVC(T, a, n, ...) \
  auto a = vector(n, vector<T>(__VA_ARGS__));
#define VVVC(T, a, n, m, ...) \
  auto a = vector(n, vector(m, vector<T>(__VA_ARGS__)));
#define VVVVC(T, a, n, m, l, ...) \
  auto a = \
    vector(n, vector(m, vector(l, vector<T>(__VA_ARGS__))));
#define be begin()
#define en end()
#define all(a) (a).be, (a).en
#define rbe rbegin()
#define ren rend()
#define allr(a) a.rbe, a.ren
#include <algorithm>
using std::sort;
template<class A>
void sort(A& a) { sort(all(a)); }
#include <algorithm>
using std::sort;
template<class A>
void sortr(A& a) { sort(allr(a)); }
#include <algorithm>
using std::reverse;
template<class A>
void reverse(A& a) { reverse(all(a)); }
#define eval_0(a, ...) a
#define eval_1(a, b, ...) b
#define eval_2(a, b, c, ...) c
#define eval_3(a, b, c, d, ...) d
#define eval_4(a, b, c, d, e, ...) e
#define eval_5(a, b, c, d, e, f, ...) f
#define eval_6(a, b, c, d, e, f, g, ...) g
#define iter_1(a, A) for (auto&& a : A)
#define iter_2(a, b, A) for (auto&& [a, b] : A)
#define iter_3(a, b, c, A) for (auto&& [a, b, c] : A)
#define iter_4(a, b, c, d, A) for (auto&& [a, b, c, d] : A)
#define iter_5(a, b, c, d, e, A) \
  for (auto&& [a, b, c, d, e] : A)
#define iter(...) \
  eval_6(__VA_ARGS__, iter_5, iter_4, iter_3, iter_2, iter_1)( \
    __VA_ARGS__ \
  )
#define pb push_back
#define eb emplace_back
#define emp emplace
#include <numeric>
using std::accumulate;
template<class T, class U>
T sum(const vc<U>& a) { return accumulate(all(a), T(0)); }
#define loop while (1)
#define FOR_1(i, n) for (int i = 0; i < n; i++)
#define FOR_2(i, a, b) for (ll i = a; i < b; i++)
#define FOR_3(i, a, b, c) for (ll i = a; i < b; i += c)
#define FOR(...) \
  eval_4(__VA_ARGS__, FOR_3, FOR_2, FOR_1, rep)(__VA_ARGS__)
#define FORR_1(i, n) for (int i = n; i-- > 0;)
#define FORR_2(i, l, r) for (ll i = r; i-- > l;)
#define FORR_3(i, l, r, d) for (ll i = r - 1; i >= l; i -= c)
#define FORR(...) \
  eval_4(__VA_ARGS__, FORR_3, FORR_2, FORR_1)(__VA_ARGS__)
#define rep(t) for (int __ = 0; __ < t; ++__)
template <class T, class F>
T binary_search(F f, T ok, T ng) {
  while (abs(ok - ng) > 1) {
    T x = (ok + ng) / 2;
    (f(x) ? ok : ng) = x;
  }
  return ok;
}
template <typename F>
dbl binary_search_real(F f, dbl ok, dbl ng, int t = 100) {
  rep(t) {
    dbl x = (ok + ng) / 2;
    (f(x) ? ok : ng) = x;
  }
  return ok;
}
#include <algorithm>
using std::lower_bound;
using std::upper_bound;
template<class A, class T>
auto lb(A& a, const T& x) { return lower_bound(all(a), x); }
template<class A, class T>
int lbi(const A& a, const T& x) { return lb(a, x) - a.be; }
template<class A, class T>
auto ub(A& a, const T& x) { return upper_bound(all(a), x); }
template<class A, class T>
int ubi(const A& a, const T& x) { return ub(a, x) - a.be; }
#include <string>
using std::string;
using str = string;
template<class A>
int len(const A& a) { return a.size(); }
template<class T=int>
vc<T> iota(int n, T v=0) {
  vc<T> a(n);
  iota(all(a), v);
  return a;
}
#include <utility>
using std::pair;
using pii = pair<int, int>;
#include <utility>
using std::pair;
using pll = pair<ll, ll>;
using vi = vc<int>;
using vl = vc<ll>;
using vii = vc<pii>;
using vll = vc<pll>;
#define mt make_tuple
#define ins insert
template <class T, class U>
bool chmax(T& a, const U& b) { return b > a ? a = b, 1 : 0; }
template <class T, class U>
bool chmin(T& a, const U& b) { return b < a ? a = b, 1 : 0; }
#include <queue>
using std::priority_queue;
template<class T>
using max_que = priority_queue<T>;
using std::greater;
template<class T>
using min_que = priority_queue<T, vc<T>, greater<T>>;

template<class T>
T pop(min_que<T>& q) { T v = q.top(); q.pop(); return v; }
template<class T>
T pop(max_que<T>& q) { T v = q.top(); q.pop(); return v; }
#include <algorithm>
using std::max_element;
using std::min_element;
template <class A>
auto max(const A& a) { return *max_element(all(a)); }
template <class A>
auto min(const A& a) { return *min_element(all(a)); }
template <class T>
T max(const set<T>& s) {
  return *s.rbe;
}
template <class T>
T min(const set<T>& s) {
  return *s.be;
}
template <class T>
T max(const multiset<T>& s) {
  return *s.rbe;
}
template <class T>
T min(const multiset<T>& s) {
  return *s.be;
}
#include <bits/stdc++.h>
using namespace std;
template <typename... T>
constexpr auto min(T... a) {
  using U = common_type_t<T...>;
  return std::min(initializer_list<U>{a...});
}
template <typename... T>
constexpr auto max(T... a) {
  using U = common_type_t<T...>;
  return std::max(initializer_list<U>{a...});
}
#define fi first
#define se second
#include <functional>
using std::function;
template <class F>
using fn = function<F>;
template <class A>
A fancy(const A& a, const vc<int>& p) {
  int n = len(p);
  A b(n);
  FOR(i, n) b[i] = a[p[i]];
  return b;
}
template <class A>
vc<int> argsort(const A& a) {
  auto p = iota(len(a));
  sort(all(p), [&](int i, int j) {
    return a[i] == a[j] ? i < j : a[i] < a[j];
  });
  return p;
}
vc<int> argperm(const vc<int>& p) {
  int n = len(p);
  vc<int> a(n);
  FOR(i, n) a[p[i]] = i;
  return a;
}
template <class A>
int argmax(const A& a) {
  return max_element(all(a)) - a.be;
}
template <class A>
int argmin(const A& a) {
  return min_element(all(a)) - a.be;
}
template <class A>
vc<int> rankify(const A& a) {
  return argperm(argsort(a));
}
/* deprecated
*/
#include <queue>
using std::queue;
template<class T>
T pop(queue<T>& q) {
  T x = q.front();
  q.pop();
  return x;
}

#include <queue>
using std::deque;
template <class T>
T pop_front(deque<T>& q) {
  T x = q.front();
  q.pop_front();
  return x;
}
template <class T>
T pop_back(deque<T>& q) {
  T x = q.back();
  q.pop_back();
  return x;
}
template <class T>
T pop(vc<T>& a) {
  T x = a.back();
  a.pop_back();
  return x;
}
char pop(str& a) {
  char x = a.back();
  a.pop_back();
  return x;
}
class range {
  ll i, b, d;
public:
  range(ll a, ll b, ll d): i(a), b(b), d(d) {}
  range(ll a, ll b): range(a, b, a < b ? 1 : -1) {}
  range(int n): range(0, n) {}
  range& begin() { return *this; }
  range& end() { return *this; }
  range& operator++() {
    i += d;
    return *this;
  }
  bool operator!=(const range&) const {
    return d > 0 && i < b || d < 0 && i > b;
  }
  ll operator*() const { return i; }
};
template <class T>
int signum(T x) {
  return x > 0 ? 1 : x < 0 ? -1 : 0;
}
template <class T, class U>
auto divmod(T n, U k) -> pair<T, T> {
  T q = n / k;
  T r = n - q * k;
  if (signum(r) * signum(k) < 0) r += k, q--;
  return {q, r};
}
#include <random>
using std::mt19937_64;
using std::random_device;
mt19937_64 mrand(random_device{}());
int rng(int x) { return mrand() % x; }
constexpr double PI = 3.14159265358979323846;
#include <bits/stdc++.h>
using namespace std;
char to_upper(char& x) { return toupper(x); }
char to_lower(char& x) { return tolower(x); }
#include <bits/stdc++.h>
using namespace std;
string to_lower(string s) {
  iter(x, s) x = tolower(x);
  return s;
}
string to_upper(string s) {
  iter(x, s) x = toupper(x);
  return s;
}
template <class T>
vc<int> flat_zero(const vc<T>& a) {
  vc<int> p;
  FOR(i, len(a)) if (!a[i]) p.pb(i);
  return p;
}
vc<int> flat_nonzero(const vc<bool>& f) {
  int n = len(f);
  vc<int> a;
  FOR(i, n) if (f[i]) a.pb(i);
  return a;
}
template <class A>
bool is_palindrome(const A& a, int l = 0, int r = -1) {
  if (r == -1) r = len(a);
  for (; l < --r; l++)
    if (a[l] != a[r]) return 0;
  return 1;
}
template <class T, class U>
vc<T> cumsum(const vc<U>& a, int k = 1) {
  int n = len(a);
  assert(n && k >= 0);
  vc<T> s(n + k);
  s[k] = a[0];
  FOR(i, 1, n) s[k + i] = s[k + i - 1] + a[i];
  return s;
}
template <class A, class... As>
A concat(A a, const As&... bs) {
  (a.insert(a.en, all(bs)), ...);
  return a;
}
template <class A>
A unique(A a) {
  sort(a);
  a.erase(unique(all(a)), a.en);
  return a;
}
vi bincount(const vi& a) {
  vi c(max(a) + 1);
  iter(x, a) c[x]++;
  return c;
}
template <class T>
set<T> operator-(const set<T>& a, const set<T>& b) {
  set<T> c;
  set_difference(all(a), all(b), inserter(c, c.en));
  return c;
}
template <class T>
set<T> operator&(const set<T>& a, const set<T>& b) {
  set<T> c;
  set_intersection(all(a), all(b), inserter(c, c.en));
  return c;
}
template <class T>
set<T> operator|(const set<T>& a, const set<T>& b) {
  set<T> c;
  set_union(all(a), all(b), inserter(c, c.en));
  return c;
}
#include <iostream>
using namespace std;
void fastio() {
  ios::sync_with_stdio(0);
  cin.tie(0);
}
#include <iostream>
#include <iomanip>
using namespace std;
void precise_float() { cout << setprecision(18); }
template <class T, class U>
istream& operator>>(istream& i, pair<T, U>& p) {
  return i >> p.fi >> p.se;
}
#include <tuple>
#include <iostream>
using namespace std;
template <int k = 0, class T>
void scan_tup(istream& i, T& x) {
  if constexpr (tuple_size<T>::value > k) {
    i >> get<k>(x);
    scan_tup<k + 1>(i, x);
  }
}
template <class... T>
istream& operator>>(istream& i, tuple<T...>& x) {
  scan_tup(i, x);
  return i;
}
template <class I, class T>
I& operator>>(I& i, vc<T>& a) {
  iter(x, a) i >> x;
  return i;
}
#include <iostream>
using namespace std;
template <typename... T>
void scan(T&... a) { (cin >> ... >> a); }
#define VEC(T, a, n) VC(T, a, n); cin >> a;
#define V(T, a, n) VC(T, a, n); cin >> a;
#define VV(T, a, n, m) VVC(T, a, n, m); cin >> a;
#define VVV(T, a, n, m, l) VVC(T, a, n, m, l); cin >> a;
#define INT(...) int __VA_ARGS__; scan(__VA_ARGS__)
#define LL(...) ll __VA_ARGS__; scan(__VA_ARGS__)
#define DBL(...) dbl __VA_ARGS__; scan(__VA_ARGS__)
#define STR(...) str __VA_ARGS__; scan(__VA_ARGS__)
#define CHAR(...) char __VA_ARGS__; scan(__VA_ARGS__)
#define VI(a, n) V(int, a, n)
#define VL(a, n) V(ll, a, n)
#define VII(a, n) V(pii, a, n)
#define VLL(a, n) V(pll, a, n)
#define VSTR(a, n) V(str, a, n)
template <class T, size_t n>
ostream& operator<<(ostream& os, const array<T, n>& a) {
  FOR(i, n) {
    if (i) os << ' ';
    os << a[i];
  }
  return os;
}
template <class T, size_t n>
ostream& operator<<(ostream& os, array<array<T, n>, n> a) {
  FOR(i, n) os << a[i] << '\n';
  return os;
}
#include <bits/stdc++.h>
using namespace std;
template <class T, class U>
ostream& operator<<(ostream& o, pair<T, U>& p) {
  return o << p.fi << ' ' << p.se;
}
#include <bits/stdc++.h>
using namespace std;
template <int k = 0, class T>
void out_tup(ostream& o, T& x) {
  if constexpr (tuple_size<T>::value > k) {
    if constexpr (k > 0) o << ' ';
    o << get<k>(x);
    out_tup<k + 1>(o, x);
  }
}
template <class... T>
ostream& operator<<(ostream& o, tuple<T...>& x) {
  out_tup(o, x);
  return o;
}
template <class O, class T>
O& operator<<(O& o, vc<T> a) {
  FOR(i, len(a)) {
    if (i) o << ' ';
    o << a[i];
  }
  return o;
}
template <class O, class T>
O& operator<<(O& o, vvc<T> a) {
  iter(x, a) o << x << '\n';
  return o;
}
#include <iostream>
using namespace std;
template <class T, class... U>
void print(T a, U... b) {
  cout << a;
  ((cout << ' ' << b), ...);
  cout << '\n';
}
#include <iostream>
using std::cout;
#define yesno(y, n) \
  void y(bool f = 1) { cout << (f ? #y : #n) << '\n'; } \
  void n(bool f = 1) { y(!f); }
yesno(yes, no);
yesno(Yes, No);
yesno(YES, NO);
ll sum_i2(ll n, int mod) {
  ll s;
  if (n % 2 == 0 && n % 3 == 0) {
    s = (n / 6 % mod) * ((n + 1) % mod) % mod * ((2 * n + 1) % mod) % mod;
  } else if (n % 2 == 0 && n % 3 == 1) {
    s = (n / 2 % mod) * ((n + 1) % mod) % mod * ((2 * n + 1) / 3 % mod) % mod;
  } else if(n % 2 == 0) {
    s = (n / 2 % mod) * ((n + 1) / 3 % mod) % mod * ((2 * n + 1) % mod) % mod;
  } else if (n % 3 == 0) {
    s = (n / 3 % mod) * ((n + 1) / 2 % mod) % mod * ((2 * n + 1) % mod) % mod;
  } else if (n % 3 == 1) {
    s = (n % mod) * ((n + 1) / 2 % mod) % mod * ((2 * n + 1) / 3 % mod) % mod;
  } else  {
    s = (n % mod) * ((n + 1) / 6 % mod) % mod * ((2 * n + 1) % mod) % mod;
  }
  return s;
}
int main() {
  fastio();
  LL(m, n);
  VL(x, n);
  ll j = 0;
  ll ans = 0;
  const int mod = 998'244'353;
  int inv = (mod + 1) / 2;
  iter(i, x) {
    ans += sum_i2(i - j - 1, mod);
    j = i;
  }
  ans %= mod;
  ans += sum_i2(m - j, mod);
  ans %= mod;
  print(ans);
}

yukicoder

結果

テストケース

ソースコード