結果
問題 | No.2335 Jump |
ユーザー |
|
提出日時 | 2023-06-02 21:27:35 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 63 ms / 2,000 ms |
コード長 | 7,918 bytes |
コンパイル時間 | 2,376 ms |
コンパイル使用メモリ | 196,912 KB |
最終ジャッジ日時 | 2025-02-13 17:42:03 |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 20 |
ソースコード
typedef long long ll;typedef long double ld;#include <bits/stdc++.h>using namespace std;#define int long long// こっちを使おう!// __builtin_popcountll// 1<<n -> オーバーフローstruct UnionFind {vector<int> par;UnionFind() { }UnionFind(int n) : par(n, -1) { }void init(int n) { par.assign(n, -1); }int root(int x) {if (par[x] < 0) return x;else return par[x] = root(par[x]);}bool issame(int x, int y) {return root(x) == root(y);}bool merge(int x, int y) {x = root(x); y = root(y);if (x == y) return false;if (par[x] > par[y]) swap(x, y); // merge techniquepar[x] += par[y];par[y] = x;return true;}int size(int x) {return -par[root(x)];}};// Segment Treetemplate<class Monoid> struct SegTree {using Func = function<Monoid(Monoid, Monoid)>;int N;Func F;Monoid IDENTITY;int SIZE_R;vector<Monoid> dat;/* initialization */SegTree() {}SegTree(int n, const Func f, const Monoid &identity): N(n), F(f), IDENTITY(identity) {SIZE_R = 1;while (SIZE_R < n) SIZE_R *= 2;dat.assign(SIZE_R * 2, IDENTITY);}void init(int n, const Func f, const Monoid &identity) {N = n;F = f;IDENTITY = identity;SIZE_R = 1;while (SIZE_R < n) SIZE_R *= 2;dat.assign(SIZE_R * 2, IDENTITY);}/* set, a is 0-indexed *//* build(): O(N) */void set(int a, const Monoid &v) { dat[a + SIZE_R] = v; }void build() {for (int k = SIZE_R - 1; k > 0; --k)dat[k] = F(dat[k*2], dat[k*2+1]);}/* update a, a is 0-indexed, O(log N) */void update(int a, const Monoid &v) {int k = a + SIZE_R;dat[k] = v;while (k >>= 1) dat[k] = F(dat[k*2], dat[k*2+1]);}/* get [a, b), a and b are 0-indexed, O(log N) */Monoid get(int a, int b) {Monoid vleft = IDENTITY, vright = IDENTITY;for (int left = a + SIZE_R, right = b + SIZE_R; left < right;left >>= 1, right >>= 1) {if (left & 1) vleft = F(vleft, dat[left++]);if (right & 1) vright = F(dat[--right], vright);}return F(vleft, vright);}Monoid all_get() { return dat[1]; }Monoid operator [] (int a) { return dat[a + SIZE_R]; }/* get max r that f(get(l, r)) = True (0-indexed), O(log N) *//* f(IDENTITY) need to be True */int max_right(const function<bool(Monoid)> f, int l = 0) {if (l == N) return N;l += SIZE_R;Monoid sum = IDENTITY;do {while (l % 2 == 0) l >>= 1;if (!f(F(sum, dat[l]))) {while (l < SIZE_R) {l = l * 2;if (f(F(sum, dat[l]))) {sum = F(sum, dat[l]);++l;}}return l - SIZE_R;}sum = F(sum, dat[l]);++l;} while ((l & -l) != l); // stop if l = 2^ereturn N;}/* get min l that f(get(l, r)) = True (0-indexed), O(log N) *//* f(IDENTITY) need to be True */int min_left(const function<bool(Monoid)> f, int r = -1) {if (r == 0) return 0;if (r == -1) r = N;r += SIZE_R;Monoid sum = IDENTITY;do {--r;while (r > 1 && (r % 2)) r >>= 1;if (!f(F(dat[r], sum))) {while (r < SIZE_R) {r = r * 2 + 1;if (f(F(dat[r], sum))) {sum = F(dat[r], sum);--r;}}return r + 1 - SIZE_R;}sum = F(dat[r], sum);} while ((r & -r) != r);return 0;}/* debug */void print() {for (int i = 0; i < N; ++i) {cout << (*this)[i];if (i != N-1) cout << ",";}cout << endl;}};// modinttemplate<int MOD> struct Fp {long long val;constexpr Fp(long long v = 0) noexcept : val(v % MOD) {if (val < 0) val += MOD;}constexpr int getmod() const { return MOD; }constexpr Fp operator - () const noexcept {return val ? MOD - val : 0;}constexpr Fp operator + (const Fp& r) const noexcept { return Fp(*this) += r; }constexpr Fp operator - (const Fp& r) const noexcept { return Fp(*this) -= r; }constexpr Fp operator * (const Fp& r) const noexcept { return Fp(*this) *= r; }constexpr Fp operator / (const Fp& r) const noexcept { return Fp(*this) /= r; }constexpr Fp& operator += (const Fp& r) noexcept {val += r.val;if (val >= MOD) val -= MOD;return *this;}constexpr Fp& operator -= (const Fp& r) noexcept {val -= r.val;if (val < 0) val += MOD;return *this;}constexpr Fp& operator *= (const Fp& r) noexcept {val = val * r.val % MOD;return *this;}constexpr Fp& operator /= (const Fp& r) noexcept {long long a = r.val, b = MOD, u = 1, v = 0;while (b) {long long t = a / b;a -= t * b, swap(a, b);u -= t * v, swap(u, v);}val = val * u % MOD;if (val < 0) val += MOD;return *this;}constexpr bool operator == (const Fp& r) const noexcept {return this->val == r.val;}constexpr bool operator != (const Fp& r) const noexcept {return this->val != r.val;}friend constexpr istream& operator >> (istream& is, Fp<MOD>& x) noexcept {is >> x.val;x.val %= MOD;if (x.val < 0) x.val += MOD;return is;}friend constexpr ostream& operator << (ostream& os, const Fp<MOD>& x) noexcept {return os << x.val;}friend constexpr Fp<MOD> modpow(const Fp<MOD>& r, long long n) noexcept {if (n == 0) return 1;if (n < 0) return modpow(modinv(r), -n);auto t = modpow(r, n / 2);t = t * t;if (n & 1) t = t * r;return t;}friend constexpr Fp<MOD> modinv(const Fp<MOD>& r) noexcept {long long a = r.val, b = MOD, u = 1, v = 0;while (b) {long long t = a / b;a -= t * b, swap(a, b);u -= t * v, swap(u, v);}return Fp<MOD>(u);}};// const int MOD = 1000000007;const int MOD = 998244353;// const int MOD = 0; // Change!using mint = Fp<MOD>;// Binomial coefficienttemplate<class T> struct BiCoef {vector<T> fact_, inv_, finv_;constexpr BiCoef() {}constexpr BiCoef(int n) noexcept : fact_(n, 1), inv_(n, 1), finv_(n, 1) {init(n);}constexpr void init(int n) noexcept {fact_.assign(n, 1), inv_.assign(n, 1), finv_.assign(n, 1);int MOD = fact_[0].getmod();for(int i = 2; i < n; i++){fact_[i] = fact_[i-1] * i;inv_[i] = -inv_[MOD%i] * (MOD/i);finv_[i] = finv_[i-1] * inv_[i];}}constexpr T com(int n, int k) const noexcept {if (n < k || n < 0 || k < 0) return 0;return fact_[n] * finv_[k] * finv_[n-k];}constexpr T fact(int n) const noexcept {if (n < 0) return 0;return fact_[n];}constexpr T inv(int n) const noexcept {if (n < 0) return 0;return inv_[n];}constexpr T finv(int n) const noexcept {if (n < 0) return 0;return finv_[n];}};BiCoef<mint> bc;signed main(){ll n;std::cin >> n;vector<ll> a(n);for (int i = 0; i < n; i++) {std::cin >> a[i];}std::cout << a[n-1]-n << std::endl;}