結果
| 問題 | No.2739 Time is money |
| ユーザー |
 ZOI-dayo
|
| 提出日時 | 2024-04-20 20:24:27 |
| 言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 52,421 bytes |
| コンパイル時間 | 11,075 ms |
| コンパイル使用メモリ | 494,588 KB |
| 実行使用メモリ | 23,184 KB |
| 最終ジャッジ日時 | 2024-10-12 18:29:12 |
| 合計ジャッジ時間 | 17,941 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
10,496 KB |
| testcase_01 | AC | 2 ms
5,248 KB |
| testcase_02 | AC | 80 ms
13,440 KB |
| testcase_03 | AC | 142 ms
17,444 KB |
| testcase_04 | AC | 75 ms
13,184 KB |
| testcase_05 | AC | 96 ms
13,236 KB |
| testcase_06 | AC | 139 ms
16,088 KB |
| testcase_07 | AC | 195 ms
20,144 KB |
| testcase_08 | AC | 165 ms
19,968 KB |
| testcase_09 | AC | 180 ms
20,224 KB |
| testcase_10 | AC | 157 ms
19,828 KB |
| testcase_11 | AC | 223 ms
20,416 KB |
| testcase_12 | AC | 145 ms
18,816 KB |
| testcase_13 | AC | 150 ms
19,072 KB |
| testcase_14 | AC | 139 ms
18,944 KB |
| testcase_15 | TLE | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
ソースコード
#line 2 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/common/template.hpp"
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#line 2 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/common/alias.hpp"
#include <boost/multiprecision/cpp_int.hpp>
#include <bits/stdc++.h>
using namespace std;
// using namespace std::views;
// using namespace boost::multiprecision;
// --- 型エイリアス ---
using ll = long long;
using ull = unsigned long long;
template <typename T> using vec = vector<T>;
template <typename T> using vvec = vector<vector<T>>;
template <typename T> using p_queue = priority_queue<T>;
template <typename T> using rp_queue = priority_queue<T, vec<T>, greater<T>>;
using bint = boost::multiprecision::cpp_int;
// --- 黒魔術 ---
#define int ll
// --- 制御マクロ ---
#define rep(i, n) for (ll i = 0; i < n; ++i)
#define all(v) begin(v), end(v)
// #define BIT(n) (1LL << (n))
#define MAX(type) numeric_limits<type>::max()
#define MIN(type) numeric_limits<type>::min()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
// --- 定数 ---
constexpr ll INF = 1LL << 60;
inline signed bit_width(ll x) { return bit_width((ull)x); }
inline ull bit_ceil(ll x) { return bit_ceil((ull)x); }
#line 2 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/common/concepts.hpp"
#line 4 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/common/concepts.hpp"
template <class T>
concept addable = requires(T a, T b) {
{ a + b } -> convertible_to<T>;
};
#line 2 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/common/debug.hpp"
#line 4 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/common/debug.hpp"
// --- デバッグ ---
#ifndef ONLINE_JUDGE
// #define printd(x) cerr << #x << ": " << x << endl;
const string _TERM_ESC = "\033";
const string _TERM_BOLD = _TERM_ESC + "[1m";
const string _TERM_DECO_RESET = _TERM_ESC + "[0m";
const string _TERM_FORE_RED = _TERM_ESC + "[31m";
const string _TERM_FORE_RESET = _TERM_ESC + "[39m";
const string _TERM_BACK_RED = _TERM_ESC + "[41m";
const string _TERM_BACK_RESET = _TERM_ESC + "[49m";
#define line_debug() cerr << "line: " << __LINE__ << endl;
#define coutd(x) cerr << "[debug] " << x;
#define printd(x) \
cerr << _TERM_BOLD << _TERM_BACK_RED << "[debug] " << (#x) << " = " << (x) \
<< _TERM_BACK_RESET << _TERM_DECO_RESET << endl;
#else
#define line_debug() ;
#define coutd(x) ;
#define printd(x) ;
#endif
#line 2 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/common/int128_t.hpp"
#line 4 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/common/int128_t.hpp"
using int128_t = __int128_t;
using uint128_t = __uint128_t;
using lll = int128_t;
using ulll = uint128_t;
// https://kenkoooo.hatenablog.com/entry/2016/11/30/163533
ostream &operator<<(ostream &dest, lll value) {
ostream::sentry s(dest);
if (s) {
lll tmp = value < 0 ? -value : value;
char buffer[128];
char *d = end(buffer);
do {
--d;
*d = "0123456789"[tmp % 10];
tmp /= 10;
} while (tmp != 0);
if (value < 0) {
--d;
*d = '-';
}
int len = end(buffer) - d;
if (dest.rdbuf()->sputn(d, len) != len) {
dest.setstate(ios_base::badbit);
}
}
return dest;
}
lll string_to_lll(string &s) {
lll ret = 0;
for (int i = 0; i < s.length(); i++)
if ('0' <= s[i] && s[i] <= '9')
ret = 10 * ret + s[i] - '0';
return ret;
}
istream &operator>>(istream &src, lll &value) {
string s;
src >> s;
value = string_to_lll(s);
return src;
}
#line 2 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/common/print.hpp"
#line 4 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/common/print.hpp"
// ---------------
// ----- TOC -----
template <typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p);
template <typename T1, typename T2>
istream &operator>>(istream &is, pair<T1, T2> &p);
template <typename T> ostream &operator<<(ostream &os, const vector<T> &v);
template <typename T>
ostream &operator<<(ostream &os, const vector<vector<T>> &v);
template <typename T>
ostream &operator<<(ostream &os, const vector<vector<vector<T>>> &v);
template <typename T> istream &operator>>(istream &is, vector<T> &v);
template <typename T, typename S>
ostream &operator<<(ostream &os, const map<T, S> &mp);
template <typename T> ostream &operator<<(ostream &os, const set<T> &st);
template <typename T> ostream &operator<<(ostream &os, const multiset<T> &st);
template <typename T> ostream &operator<<(ostream &os, queue<T> q);
template <typename T> ostream &operator<<(ostream &os, deque<T> q);
template <typename T> ostream &operator<<(ostream &os, stack<T> st);
template <class T, class Container, class Compare>
ostream &operator<<(ostream &os, priority_queue<T, Container, Compare> pq);
// --- END TOC ---
// ---------------
template <typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
os << "(" << p.first << "," << p.second << ")";
return os;
}
template <typename T1, typename T2>
istream &operator>>(istream &is, pair<T1, T2> &p) {
is >> p.first >> p.second;
return is;
}
template <typename T> ostream &operator<<(ostream &os, const vector<T> &v) {
os << "[";
for (int i = 0; i < (int)v.size(); i++) {
os << v[i] << (i + 1 != (int)v.size() ? ", " : "]");
}
return os;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<vector<T>> &v) {
for (int i = 0; i < (int)v.size(); i++) {
os << v[i] << endl;
}
return os;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<vector<vector<T>>> &v) {
for (int i = 0; i < (int)v.size(); i++) {
os << "i = " << i << endl;
os << v[i];
}
return os;
}
template <typename T> istream &operator>>(istream &is, vector<T> &v) {
for (T &in : v)
is >> in;
return is;
}
template <typename T, typename S>
ostream &operator<<(ostream &os, const map<T, S> &mp) {
for (auto &[key, val] : mp) {
os << key << ":" << val << " ";
}
return os;
}
template <typename T> ostream &operator<<(ostream &os, const set<T> &st) {
os << "{";
auto itr = st.begin();
for (int i = 0; i < (int)st.size(); i++) {
os << *itr << (i + 1 != (int)st.size() ? ", " : "}");
itr++;
}
return os;
}
template <typename T> ostream &operator<<(ostream &os, const multiset<T> &st) {
auto itr = st.begin();
for (int i = 0; i < (int)st.size(); i++) {
os << *itr << (i + 1 != (int)st.size() ? " " : "");
itr++;
}
return os;
}
template <typename T> ostream &operator<<(ostream &os, queue<T> q) {
while (q.size()) {
os << q.front() << " ";
q.pop();
}
return os;
}
template <typename T> ostream &operator<<(ostream &os, deque<T> q) {
while (q.size()) {
os << q.front() << " ";
q.pop_front();
}
return os;
}
template <typename T> ostream &operator<<(ostream &os, stack<T> st) {
while (st.size()) {
os << st.top() << " ";
st.pop();
}
return os;
}
template <class T, class Container, class Compare>
ostream &operator<<(ostream &os, priority_queue<T, Container, Compare> pq) {
while (pq.size()) {
os << pq.top() << " ";
pq.pop();
}
return os;
}
#line 2 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/common/util.hpp"
#line 5 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/common/util.hpp"
// --- Utils ---
// 二分探索
template <typename T>
inline T bin_search(T ok, T ng, const function<bool(T)> is_ok) {
assert(is_ok(ok));
assert(!is_ok(ng));
assert(ok < ng);
while (abs(ok - ng) > 1) {
T mid = (ok + ng) / 2;
if (is_ok(mid))
ok = mid;
else
ng = mid;
}
return ok;
}
// 順列全探索
inline void rep_perm(int n, function<void(vec<int> &)> f) {
vec<int> v(n);
iota(v.begin(), v.end(), 0);
do {
f(v);
} while (next_permutation(v.begin(), v.end()));
}
inline void rep_bit(int n, function<void(int)> f) { rep(i, 1LL << n) f(i); }
// 配列 to string
template <typename T> inline string join(const vec<T> &v, string sep = " ") {
string res = "";
rep(i, v.size()) res += to_string(v[i]) + (i == v.size() - 1 ? "" : sep);
return res;
}
template <typename T>
inline void join_out(ostream &os, const vec<T> &v, string sep = " ",
string end = "\n") {
int n = v.size();
rep(i, n) os << v[i] << (i == n - 1 ? end : sep);
}
template <typename T>
inline void transform(vec<T> &src, function<void(T &)> f) {
for (auto &val : src)
f(val);
}
// ベース指定ceil
inline ll ceil(ll x, ll base) { return (x + base - 1) / base * base; }
// ベース指定floor
inline ll floor(ll x, ll base) { return x / base * base; }
// 合計値を求める
// ll sum(const vec<ll> &v) { return accumulate(all(v), 0LL); }
template <addable T> T sum(const vec<T> &v) { return accumulate(all(v), T()); }
// 可変引数min
template <class... T> auto min(T... a) {
return min(initializer_list<common_type_t<T...>>{a...});
}
// 可変引数max
template <class... T> auto max(T... a) {
return max(initializer_list<common_type_t<T...>>{a...});
}
template <class T> bool chmax(T &a, const T &b) {
if (a < b) {
a = b;
return 1;
}
return 0;
}
template <class T> bool chmin(T &a, const T &b) {
if (b < a) {
a = b;
return 1;
}
return 0;
}
// 3項間不等式
// 広義単調増加
inline bool is_increasing(int x, int y, int z) { return x <= y && y <= z; }
// 半開区間[x, z)にyが含まれるか?
inline bool is_contained(int x, int y, int z) { return x <= y && y < z; }
// 頂点(x, y)が範囲に含まれるか
inline bool is_contained(int H, int W, int x, int y) {
return is_contained(0, x, H) && is_contained(0, y, W);
}
// rootに対し、aとbが同じ側にあるか (=は含まない)
inline bool is_same_side(int root, int a, int b) {
return (root < a) == (root < b);
}
// vector継承にする?
template <typename T> struct vec_accumulate : public vec<T> {
explicit vec_accumulate(vec<T> &v) : vec<T>(v.size()) {
assert(v.size() > 0);
this->at(0) = v[0];
for (int i = 1; i < v.size(); ++i)
this->at(i) = this->at(i - 1) + v[i];
}
// [0, i]の和
// なので、-1 <= i < size()
T operator[](int i) {
assert(is_contained(-1, i, this->size()));
if (i == -1)
return T();
return this->at(i);
}
};
// vector func
template <typename T> inline void unique_erase(vec<T> &v) {
sort(all(v));
v.erase(unique(all(v)), v.end());
}
void io_setup() {
cin.tie(nullptr);
ios::sync_with_stdio(false);
cout << std::fixed << std::setprecision(15);
}
#line 12 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/common/template.hpp"
#line 2 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/math/pow.hpp"
#line 5 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/math/pow.hpp"
// 繰り返し2乗法
template <integral T, integral F> constexpr T pow(T a, F n) {
T ans = 1;
while (n > 0) {
if (n & 1)
ans *= a;
a *= a;
n >>= 1;
}
return ans;
}
constexpr ll powm(ll a, ll n, const ll mod) {
lll ans = 1;
while (n > 0) {
if (n & 1)
ans = ans * a % mod;
a = ((lll)a) * a % mod;
n >>= 1;
}
return ans;
}
#line 2 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/all.hpp"
#line 2 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/2d/all.hpp"
#line 3 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/2d/point.hpp"
class Point {
public:
int x, y;
Point() : x(0), y(0) {}
Point(int x, int y) : x(x), y(y) {}
Point up() const { return Point(x - 1, y); }
Point down() const { return Point(x + 1, y); }
Point left() const { return Point(x, y - 1); }
Point right() const { return Point(x, y + 1); }
Point upper_left() const { return Point(x - 1, y - 1); }
Point upper_right() const { return Point(x - 1, y + 1); }
Point lower_left() const { return Point(x + 1, y - 1); }
Point lower_right() const { return Point(x + 1, y + 1); }
vec<Point> around4() const { return {up(), down(), left(), right()}; }
vec<Point> around8() const {
return {up(), up().right(), right(), right().down(),
down(), down().left(), left(), left().up()};
}
int manhattan() const { return std::abs(x) + std::abs(y); }
int eucurid2() const { return x * x + y * y; }
bool operator==(const Point &p) const { return x == p.x && y == p.y; }
bool operator!=(const Point &p) const { return !(*this == p); }
void operator+=(const Point &p) {
x += p.x;
y += p.y;
}
void operator-=(const Point &p) {
x -= p.x;
y -= p.y;
}
Point operator+(const Point &p) const { return Point(x + p.x, y + p.y); }
Point operator-(const Point &p) const { return Point(x - p.x, y - p.y); }
bool operator<(const Point &p) const {
return x == p.x ? y < p.y : x < p.x;
}
bool operator>(const Point &p) const {
return x == p.x ? y > p.y : x > p.x;
}
};
ostream &operator<<(ostream &os, const Point &p) {
os << p.x << p.y;
return os;
}
istream &operator>>(istream &is, Point &p) {
is >> p.x >> p.y;
return is;
}
inline bool is_contained(int H, int W, Point p) {
return is_contained(H, W, p.x, p.y);
}
#line 4 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/2d/area.hpp"
class Area {
public:
int H, W;
bool allow_outside = false;
char out_val;
Area(int H, int W) : H(H), W(W), data(vector(H, string(W, '.'))) {}
Area(int H, int W, char out_val)
: H(H), W(W), data(vector(H, string(W, '.'))), allow_outside(true),
out_val(out_val) {}
string &operator[](int i) { return data[i]; }
// 時計回りで90度回転
Area rotated90() const {
Area ret(W, H);
rep(i, H) rep(j, W) ret[j][H - i - 1] = data[i][j];
return ret;
}
void rotate90() {
assert(H == W);
data = rotated90().data;
}
char at(int x, int y) {
if (is_contained(H, W, x, y))
return data[x][y];
else if (allow_outside)
return out_val;
else {
cerr << "[Area::at] out of range" << endl;
assert(false);
}
}
void set(int x, int y, char val) {
if (is_contained(H, W, x, y))
data[x][y] = val;
else if (allow_outside)
return;
else {
cerr << "[Area::set] out of range" << endl;
assert(false);
}
}
bool contains(int x, int y) const { return is_contained(H, W, x, y); }
bool contains(Point p) const { return is_contained(H, W, p.x, p.y); }
private:
vec<string> data;
};
ostream &operator<<(ostream &os, Area &a) {
rep(i, a.H) os << a[i] << endl;
return os;
}
istream &operator>>(istream &is, Area &a) {
rep(i, a.H) is >> a[i];
return is;
}
#line 2 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/2d/rect.hpp"
class Rect {
public:
int x, y, w, h;
Rect(int x, int y, int w, int h) : x(x), y(y), w(w), h(h) {}
int area() const { return w * h; }
};
#line 2 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/3d/all.hpp"
#line 2 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/3d/cuboid.hpp"
class Cuboid {
public:
int x, y, z;
int w, h, d;
Cuboid(int x, int y, int z, int w, int h, int d)
: x(x), y(y), z(z), w(w), h(h), d(d) {}
Cuboid(int w, int h, int d) : x(0), y(0), z(0), w(w), h(h), d(d) {}
int volume() { return w * h * d; }
Cuboid intersect(Cuboid c) {
int x1 = max(x, c.x);
int y1 = max(y, c.y);
int z1 = max(z, c.z);
int x2 = min(x + w, c.x + c.w);
int y2 = min(y + h, c.y + c.h);
int z2 = min(z + d, c.z + c.d);
if (x2 <= x1 || y2 <= y1 || z2 <= z1) {
return Cuboid(0, 0, 0, 0, 0, 0);
}
return Cuboid(x1, y1, z1, x2 - x1, y2 - y1, z2 - z1);
}
void move(int dx, int dy, int dz) {
x += dx;
y += dy;
z += dz;
}
static Cuboid intersect(Cuboid &a, Cuboid &b) { return a.intersect(b); }
static Cuboid intersect(initializer_list<Cuboid> cuboids) {
auto it = cuboids.begin();
Cuboid c = *it;
it++;
for (; it != cuboids.end(); it++) {
c = c.intersect(*it);
}
return c;
}
};
#line 2 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/convolution/all.hpp"
// #include "convolution.hpp"
#line 2 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/all.hpp"
#line 2 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/comp.hpp"
#line 4 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/comp.hpp"
// https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/4/DSL_4_A
template <typename T> struct comp {
private:
const int _n;
int _cmp_n;
vec<T> _raw, _comp;
public:
explicit comp(const vec<T> &src)
: _n(src.size()), _cmp_n(0), _raw(src), _comp(_n, 0) {
sort(_raw.begin(), _raw.end());
_raw.erase(unique(_raw.begin(), _raw.end()), _raw.end());
_cmp_n = _raw.size();
rep(i, _n) _comp[i] =
lower_bound(_raw.begin(), _raw.end(), src[i]) - _raw.begin();
}
inline int size() const { return _n; }
inline int cmp_size() const { return _cmp_n; }
inline T get_raw(int complessed) {
assert(0 <= complessed && complessed < _cmp_n);
return _raw[complessed];
}
inline T operator[](int i) {
assert(0 <= i && i < _n);
return _comp[i];
}
inline T get_comp(int raw) {
return lower_bound(_raw.begin(), _raw.end(), raw) - _raw.begin();
}
};
#line 2 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/fenwick-tree.hpp"
#line 4 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/fenwick-tree.hpp"
template <typename T> struct FenwickTree {
private:
T _n;
vec<T> _data;
public:
explicit FenwickTree(T n) : _n(n), _data(n + 1, 0) {}
explicit FenwickTree(const vec<T> &src) : _n(src.size()), _data(_n + 1, 0) {
rep(i, _n) add(i, src[i]);
}
void add(int i, T val) {
i++;
while (i <= _n) {
_data[i] += val;
i += i & -i;
}
}
// [0, i]
int sum(int i) const {
i++;
T ans = 0;
while (i > 0) {
ans += _data[i];
i -= i & -i;
}
return ans;
}
// [l, r)
int sum(int l, int r) const { return sum(r - 1) - sum(l - 1); }
};
#line 2 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/imos.hpp"
#line 4 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/imos.hpp"
template <typename T> struct imos {
private:
const int _n;
vec<T> _data;
bool _is_build = false;
public:
explicit imos(int n) : _n(n), _data(_n + 1, 0) {}
explicit imos(vec<T> src) : _n(src.size()), _data(_n + 1, 0) {
rep(i, _n) add(i, src[i]);
}
inline int size() const { return _n; }
inline void add(int l, int r, T x) {
assert(!_is_build);
assert(l < r);
assert(0 <= l && r <= _n);
_data[l] += x;
_data[r] -= x;
}
inline void add(int i, T x) {
assert(!_is_build);
assert(0 <= i && i < _n);
add(i, i + 1, x);
}
inline void build() {
rep(i, _n) _data[i + 1] += _data[i];
_is_build = true;
}
inline T get(int i) {
assert(0 <= i && i < _n);
if (!_is_build)
build();
return _data[i];
}
friend ostream &operator<<(ostream &os, const imos<T> &a) {
if (!a._is_build) {
os << "not builded";
return os;
}
os << a._data;
return os;
}
};
#line 2 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/imos2d.hpp"
#line 5 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/imos2d.hpp"
template <typename T> struct imos2d {
private:
const int _H, _W;
vvec<T> _data;
bool _is_build = false;
public:
explicit imos2d(int H, int W)
: _H(H), _W(W), _data(_H + 1, vec<T>(_W + 1, 0)) {}
explicit imos2d(vvec<T> src)
: _H(src.size()), _W(src[0].size()), _data(_H + 1, vec<T>(_W + 1, 0)) {
rep(x, _H) rep(y, _W) add({x, y}, src[x][y]);
}
inline pair<int, int> size() const { return {_H, _W}; }
// 半開区間
inline void add(Point a, Point b, T x) {
assert(!_is_build);
assert(a.x < b.x && a.y < b.y);
assert(is_contained(_H, _W, a) && is_contained(_H, _W, b.upper_left()));
_data[a.x][a.y] += x;
_data[a.x][b.y] -= x;
_data[b.x][a.y] -= x;
_data[b.x][b.y] += x;
}
inline void add(Point a, T x) {
assert(!_is_build);
assert(is_contained(_H, _W, a));
add(a, a.lower_right(), x);
}
inline void build() {
rep(x, _H) rep(y, _W) _data[x][y + 1] += _data[x][y];
rep(y, _W) rep(x, _H) _data[x + 1][y] += _data[x][y];
_is_build = true;
}
inline T get(Point p) const {
assert(is_contained(_H, _W, p));
assert(_is_build);
return _data[p.x][p.y];
}
};
template <typename T> ostream &operator<<(ostream &os, const imos2d<T> &im) {
rep(x, im.size().first) {
rep(y, im.size().second) { os << im.get({x, y}) << " "; }
os << endl;
}
return os;
}
#line 2 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/lazy-segment-tree.hpp"
#line 2 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/monoid/monofunc.hpp"
#line 2 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/monoid/monoid.hpp"
#line 4 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/monoid/monoid.hpp"
/*
template <class M>
concept MonoidConcept = requires(M &x, M::T a, M::T b) {
typename M::T;
{ M::e() } -> std::same_as<typename M::T>;
{ M::op(a, b) } -> std::same_as<typename M::T>;
};
*/
template <class Type> class Monoid {
public:
Monoid() = default;
using T = Type;
virtual T e() const = 0;
virtual T op(T a, T b) const = 0;
};
template <class M>
concept MonoidConcept = requires(M &x, typename M::T a, typename M::T b) {
// derived_from<M, Monoid<typename M::T>>;
typename M::T;
{ x.e() } -> std::same_as<typename M::T>;
{ x.op(a, b) } -> std::same_as<typename M::T>;
};
#line 4 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/monoid/monofunc.hpp"
template <class Type, MonoidConcept Mono> class Monofunc {
public:
Monofunc() = default;
using T = Type;
using M = Mono;
using MT = typename M::T;
virtual T id() const = 0;
virtual MT apply(T a, MT b) const = 0;
virtual T merge(T before, T after) const = 0;
};
template <class M>
concept MonofuncConcept = requires(M &x, typename M::T before,
typename M::T after, typename M::MT mono) {
typename M::T;
typename M::M;
typename M::MT;
{ x.id() } -> std::same_as<typename M::T>;
{ x.apply(before, mono) } -> std::same_as<typename M::MT>;
{ x.merge(before, after) } -> std::same_as<typename M::T>;
};
#line 5 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/lazy-segment-tree.hpp"
// 参考 https://qiita.com/ningenMe/items/bf66de877e3b97d35862
// T : Nodeの型, F : 操作情報
template <MonofuncConcept F> struct LazySegmentTree {
private:
using M = typename F::M;
using FT = typename F::T;
using MT = typename M::T;
// 単位元 デフォルトでは、min(a, e) = min(e, a) = a
const MT e;
const FT id;
// Monoids
const M _monoid;
const F _monofunc;
// 演算
// const function<T(T, T)> op;
// const function<T(F, T)> update;
// const function<F(F, F)> merge;
// 要素数
int32_t _n;
int32_t _height;
// SefTreeのデータ
vec<MT> _data;
vec<FT> _lazy;
// 自分の遅延を解消して子に伝搬する
inline void eval(int32_t k) {
if (_lazy[k] == id)
return;
_data[k] = _monofunc.apply(_lazy[k], _data[k]);
if (k < _n) {
_lazy[k << 1 | 0] = _monofunc.merge(_lazy[k << 1 | 0], _lazy[k]);
_lazy[k << 1 | 1] = _monofunc.merge(_lazy[k << 1 | 1], _lazy[k]);
}
_lazy[k] = id;
}
public:
// n: 要素数, e: 単位元, id: 操作情報の単位元, op: 演算, update:
// ノードの更新(fn,val->val), merge:
// 操作aがすでに行われている状態に操作bを適用したときの操作
// TODO: 2つの実装が別れているのをどうにかする
explicit inline LazySegmentTree(const int32_t n)
: _monoid(M()), _monofunc(F()), e(_monoid.e()), id(_monofunc.id()) {
_n = 1;
_height = 1;
while (_n < n)
_n <<= 1, _height++;
_data = vec<MT>(_n << 1, e);
_lazy = vec<FT>(_n << 1, id);
}
explicit inline LazySegmentTree(vec<MT> &data)
: _monoid(M()), _monofunc(F()), e(_monoid.e()), id(_monofunc.id()) {
_n = 1;
_height = 1;
while (_n < data.size())
_n <<= 1, _height++;
_data = vec<MT>(_n << 1, e);
_lazy = vec<FT>(_n << 1, id);
rep(i, data.size()) _data[i + _n] = data[i];
for (int i = _n - 1; i > 0; --i)
_data[i] = _monoid.op(_data[i << 1], _data[i << 1 | 1]);
}
/*
inline LazySegmentTree(const T e, const F id,
const function<T(T, T)> op,
const function<T(F, T)> update,
const function<F(F, F)> merge,
vec<T> &v)
: e(e), id(id), op(op), update(update), merge(merge) {
_n = 1;
_height = 1;
while (_n < v.size())
_n <<= 1, _height++;
_data.resize(_n << 1, e);
for(int i=0; i<v.size(); ++i) _data[i + _n] = v[i];
_lazy = vec<F>(_n << 1, id);
}
*/
inline void set(int32_t l, int32_t r, FT f) {
/*
eval(k);
if (l <= a && b <= r) { // 完全に内側
_lazy[k] = merge(f, _lazy[k]);
eval(k);
} else if (a < r && l < b) { // 一部区間が被る
_set(l, r, f, (k << 1) + 1, a, (a + b) >> 1);
_set(l, r, f, (k << 1) + 2, (a + b) >> 1, b);
_data[k] = op(_data[(k << 1) + 1], _data[(k << 1) + 2]);
}
*/
// a, bはseg-index [a,b]
int32_t a = l + _n, b = r + _n - 1;
// 上から下へとlazyを伝搬させる
for (int32_t i = _height; 0 < i; --i)
eval(a >> i), eval(b >> i);
// bを [a, b]から[a, b)にする
for (b++; a < b; a >>= 1, b >>= 1) {
if (a & 1)
_lazy[a] = _monofunc.merge(_lazy[a], f), eval(a), a++;
if (b & 1)
--b, _lazy[b] = _monofunc.merge(_lazy[b], f), eval(b);
}
// a, bをseg-index [a,b]に戻す
a = l + _n, b = r + _n - 1;
// a,bを親に移しつつ、aが実在頂点の間
while ((a >>= 1), (b >>= 1), a) {
if (_lazy[a] == id) {
// _data[(a << 1) | 0] = update(_lazy[(a << 1) | 0], _data[(a << 1) |
// 0]); _data[(a << 1) | 1] = update(_lazy[(a << 1) | 1], _data[(a << 1)
// | 1]); _data[a] = op(_data[(a << 1) | 0], _data[(a << 1) | 1]);
_data[a] = _monoid.op(
_monofunc.apply(_lazy[(a << 1) | 0], _data[(a << 1) | 0]),
_monofunc.apply(_lazy[(a << 1) | 1], _data[(a << 1) | 1]));
}
if (_lazy[b] == id) {
// _data[(b << 1) | 0] = update(_lazy[(b << 1) | 0], _data[(b << 1) |
// 0]); _data[(b << 1) | 1] = update(_lazy[(b << 1) | 1], _data[(b << 1)
// | 1]); _data[b] = op(_data[(b << 1) | 0], _data[(b << 1) | 1]);
_data[b] = _monoid.op(
_monofunc.apply(_lazy[(b << 1) | 0], _data[(b << 1) | 0]),
_monofunc.apply(_lazy[(b << 1) | 1], _data[(b << 1) | 1]));
}
}
}
// [l, r)の区間に対するクエリを処理する
// kはSegTree上のindex
inline MT query(int32_t l, int32_t r) {
// ↓再帰
/*
eval(k);
if (r <= a || b <= l)
return e;
if (l <= a && b <= r)
return _data[k];
T l_val = _query(l, r, (k << 1) + 1, a, (a + b) >> 1);
T r_val = _query(l, r, (k << 1) + 2, (a + b) >> 1, b);
return op(l_val, r_val);
*/
// a, bはseg-index [a,b]
int32_t a = l + _n, b = r + _n - 1;
// 上から下へとlazyを伝搬させる
for (int32_t i = _height; 0 <= i; --i)
eval(a >> i), eval(b >> i);
// line_debug();
// printd(_data);
// printd(_lazy);
MT vl = e, vr = e;
// bを [a, b]から[a, b)にする
for (b++; a < b; a >>= 1, b >>= 1) {
if (a & 1)
vl = _monoid.op(vl, _monofunc.apply(_lazy[a], _data[a])), a++;
if (b & 1)
b--, vr = _monoid.op(_monofunc.apply(_lazy[b], _data[b]), vr);
}
return _monoid.op(vl, vr);
}
inline MT get(int32_t i) { return query(i, i + 1); }
};
/*
template <typename T, typename F> using LazySegtree = LazySegmentTree<T, F>;
template <typename T, typename F> inline LazySegtree<T, F> RMQLazySeg(int n) {
return LazySegmentTree<T, F>(
n, numeric_limits<T>::max(), 0, [](T a, T b) { return min(a, b); },
[](F a, T b) { return b + a; }, [](F a, F b) { return b + a; });
}
*/
#line 2 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/segment-tree.hpp"
#line 5 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/segment-tree.hpp"
// 参考: https://qiita.com/ningenMe/items/bf66de877e3b97d35862
template <MonoidConcept M> struct SegmentTree {
using T = typename M::T;
private:
M _monoid;
T e;
// 要素数
int _n;
// SegTreeのノード上のデータ
vec<T> _data;
public:
explicit SegmentTree(int n) : _n(1), _monoid(M()), e(_monoid.e()) {
while (_n < n)
_n *= 2;
_data = vec<T>(2 * _n, e);
}
explicit SegmentTree(const vec<T> &v) : _n(1), _monoid(M()), e(_monoid.e()) {
while (_n < v.size())
_n *= 2;
_data = vec<T>(2 * _n, e);
rep(i, v.size()) _data[i + _n] = v[i];
for (int i = _n - 1; i > 0; --i)
_data[i] = _monoid.op(_data[i << 1], _data[i << 1 | 1]);
}
void set(int i, T a) {
// 1段目は1, 2段目は2~3, ... , 最下段はn~(2n-1)
// より、iの最下段はi+n
i += _n;
_data[i] = a;
// i >>= 1で、iを親のindexに変更
// また、i==0となってしまうなら、i==1(頂点)であるので、終了
// i<<1は、(更新後の)iの左の子
// i<<1|1は、(更新後の)iの右の子 (+1を|1で表現)
while (i >>= 1)
_data[i] = _monoid.op(_data[i << 1], _data[i << 1 | 1]);
}
T get(int i) const { return _data[i + _n]; }
T query(int l, int r) {
T l_val = e, r_val = e;
// l, r(index)に+_nすると、最下段のseg-indexになる
// l < r == l,rをすべて含む区間にはたどり着いていない
// l/r >>= 1 : l/rを親に移動させる
for (l += _n, r += _n; l < r; l >>= 1, r >>= 1) {
// lが左の子ならば、l<=iの結果はlの親の結果であるので、計算しない
// lが右の子ならば、計算する必要がある
if (l & 1)
l_val = _monoid.op(l_val, _data[l++]);
// l++をしても、l>>1が変わることはない
// ただし、r=l+1のとき、答えはここのlである
// ので、l<rに引っかかるようにして終了させている?
// rが左の子ならば、rの親はギリギリ使われない、すなわちrの条件を満たす
// rが右の子ならば、r-1は範囲に含まれるので、計算する必要がある
if (r & 1)
r_val = _monoid.op(_data[--r], r_val);
}
return _monoid.op(l_val, r_val);
}
};
#line 2 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/union-find.hpp"
#line 4 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/union-find.hpp"
struct UnionFind {
private:
int _n;
vec<int> _parents;
vec<int> _size;
public:
explicit UnionFind(int n) : _n(n), _parents(n), _size(n, 1) {
iota(all(_parents), 0);
}
int find(int a) {
if (_parents[a] == a)
return a;
else
return _parents[a] = find(_parents[a]);
}
void merge(int a, int b) {
a = find(a);
b = find(b);
if (a != b) {
// merge後の親はa
if (_size[a] < _size[b])
swap(a, b);
_size[a] += _size[b];
_size[b] = 0;
_parents[b] = a;
}
}
int size(int a) { return _size[find(a)]; }
bool same(int a, int b) { return find(a) == find(b); }
vec<vec<int>> groups() {
vec<int> leaders(_n);
rep(i, _n) { leaders[i] = find(i); }
vec<vec<int>> res(_n);
rep(i, _n) res[i].reserve(_size[i]);
rep(i, _n) res[leaders[i]].push_back(i);
res.erase(remove_if(all(res), [&](const vec<int> &v) { return v.empty(); }),
res.end());
return res;
}
};
using UF = UnionFind;
#line 2 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/weighted-union-find.hpp"
#line 4 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/datastructure/weighted-union-find.hpp"
template <addable T> struct WeightedUnionFind {
private:
int _n;
vec<int> _parents;
vec<int> _size;
vec<T> _weight;
T weight(int i) {
find(i);
return _weight[i];
}
public:
explicit WeightedUnionFind(int n)
: _n(n), _parents(n), _size(n, 1), _weight(n) {
iota(all(_parents), 0);
}
int find(int i) {
if (_parents[i] == i)
return i;
const int root = find(_parents[i]);
_weight[i] += _weight[_parents[i]];
return _parents[i] = root;
}
void merge(int a, int b, T w) {
w += weight(a);
w -= weight(b);
a = find(a);
b = find(b);
if (a != b) {
// merge後の親はa
if (_size[a] < _size[b])
swap(a, b), w = -w;
_size[a] += _size[b];
_size[b] = 0;
_parents[b] = a;
_weight[b] = w;
}
}
T diff(int a, int b) { return weight(b) - weight(a); }
int size(int a) { return _size[find(a)]; }
bool same(int a, int b) { return find(a) == find(b); }
};
template <addable T> using WUF = WeightedUnionFind<T>;
#line 2 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/graph/cycle.hpp"
#line 2 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/graph/template.hpp"
#line 4 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/graph/template.hpp"
// Node
template <class T = ll> struct WeightedNode {
int id;
T cost = numeric_limits<T>::max();
WeightedNode(int id, T cost) : id(id), cost(cost) {}
};
template <class T = ll>
struct WeightState {
public:
int location;
T used_cost;
WeightState(int location, T used_cost)
: location(location), used_cost(used_cost) {}
bool operator<(const WeightState &n) const { return used_cost < n.used_cost; }
bool operator>(const WeightState &n) const { return used_cost > n.used_cost; }
};
// Graph
struct Graph {
private:
const int n;
const bool directed;
vec<vec<int>> edges;
public:
explicit Graph(int n, bool directed = false)
: n(n), directed(directed), edges(n) {}
inline void add_edge(int u, int v) {
edges[u].emplace_back(v);
if (!directed)
edges[v].emplace_back(u);
}
inline vec<int> &operator[](int i) { return edges[i]; }
inline int size() const { return n; }
};
template <class T = ll> struct WeightedGraph {
private:
const int n;
const bool directed;
public:
vec<vec<WeightedNode<T>>> edges;
explicit WeightedGraph(int n, bool directed = false)
: n(n), directed(directed), edges(n) {}
inline void add_edge(int u, int v, T w) {
edges[u].emplace_back(WeightedNode(v, w));
if (!directed)
edges[v].emplace_back(WeightedNode(u, w));
}
inline vec<WeightedNode<T>> &operator[](int i) { return edges[i]; }
inline int size() const { return n; }
};
// template <class T = ll> using WeightedGraph = vec<vec<WeightedNode<T>>>;
template <class T = ll> using WGraph = WeightedGraph<T>;
#line 4 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/graph/cycle.hpp"
bool has_cycle(Graph &g, int start = 0) {
vec<int> seen(g.size(), 0);
vec<int> finished(g.size(), 0);
auto dfs = [&](auto fn, int index) {
seen[index] = 1;
for (auto next : g[index]) {
if (finished[next])
continue;
if (seen[next] && !finished[next])
return true;
if (fn(fn, next))
return true;
}
finished[index] = 1;
return false;
};
return dfs(dfs, start);
}
#line 2 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/graph/depth.hpp"
#line 4 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/graph/depth.hpp"
struct TreeNodeInfo {
public:
TreeNodeInfo(int parent, int depth) : parent(parent), depth(depth) {}
int parent;
int depth;
};
vec<TreeNodeInfo> depth(Graph &graph, int root = 0) {
vec<TreeNodeInfo> result(graph.size(), TreeNodeInfo(-1, -1));
stack<int> st;
st.push(root);
result[root] = TreeNodeInfo(root, 0);
while (!st.empty()) {
int index = st.top();
st.pop();
for (auto next : graph[index]) {
if (result[next].depth != -1)
continue;
result[next] = TreeNodeInfo(index, result[index].depth + 1);
st.push(next);
}
}
return result;
}
#line 2 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/graph/diameter.hpp"
#line 4 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/graph/diameter.hpp"
int diameter(Graph &graph, int start = 0) {
vec<int> seen(graph.size(), 0);
auto dfs = [&](auto fn, int index) -> pair<int, int> {
// max-cost, index
pair<int, int> result = {0, index};
seen[index] = 1;
for (auto next : graph[index]) {
if (seen[next])
continue;
auto next_result = fn(fn, next);
next_result.first += 1;
result = max(result, next_result);
}
seen[index] = 0;
return result;
};
auto result = dfs(dfs, start);
result = dfs(dfs, result.second);
return result.first;
}
template <typename T = ll> int diameter(WGraph<T> &graph, int start = 0) {
auto dfs = [&](int index) -> pair<T, int> {
vec<T> result(graph.size(), -1);
T mx = 0;
int mx_index = index;
stack<int> st;
st.push(index);
result[index] = 0;
while (!st.empty()) {
int current = st.top();
st.pop();
for (auto next : graph[current]) {
if (result[next.id] >= 0)
continue;
st.push(next.id);
result[next.id] = result[current] + next.cost;
if (chmax(mx, result[next.id])) {
mx_index = next.id;
}
}
}
return {mx, mx_index};
};
auto result = dfs(start);
result = dfs(result.second);
return result.first;
}
#line 2 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/graph/dijkstra.hpp"
#line 4 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/graph/dijkstra.hpp"
template <typename T = ll> vec<T> dijkstra(WGraph<T> &graph, int start) {
vec<T> way(graph.size(), INF);
rp_queue<WeightState<T>> q;
q.push(WeightState<T>(start, 0));
way[start] = 0;
while (!q.empty()) {
WeightState current = q.top();
q.pop();
for (auto &next : graph[current.location]) {
T next_cost = current.used_cost + next.cost;
if (way[next.id] <= next_cost)
continue;
way[next.id] = next_cost;
q.push(WeightState<T>(next.id, way[next.id]));
}
}
return way;
}
#line 2 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/graph/lca.hpp"
struct LCA {
private:
Graph graph;
int root;
// parent[k][v] := vの2^k先の親
vec<vec<int>> parent;
vec<TreeNodeInfo> depth_data;
public:
explicit LCA(Graph &graph, int root = 0)
: graph(graph), root(root), depth_data(depth(graph, root)) {
int n = graph.size();
int logn = 1;
while ((1 << logn) < n)
logn++;
parent = vector(logn, vector(n, -1LL));
for (int i = 0; i < n; i++)
parent[0][i] = depth_data[i].parent;
// ダブリング
for (int k = 0; k + 1 < logn; k++) {
for (int i = 0; i < n; i++) {
if (parent[k][i] < 0)
parent[k + 1][i] = -1;
else
parent[k + 1][i] = parent[k][parent[k][i]];
}
}
}
int query(int u, int v) const {
if (depth_data[u].depth > depth_data[v].depth)
swap(u, v);
int logn = parent.size();
// uとvの深さが同じになるまで親を辿る
rep(k, logn) {
if ((depth_data[v].depth - depth_data[u].depth) >> k & 1) {
v = parent[k][v];
}
}
// にぶたん
if (u == v)
return u;
for (int k = logn - 1; k >= 0; k--) {
if (parent[k][u] != parent[k][v]) {
u = parent[k][u];
v = parent[k][v];
}
}
return parent[0][u];
}
};
#line 2 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/graph/topological-sort.hpp"
#line 4 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/graph/topological-sort.hpp"
vec<int> topological_sort(Graph &graph) {
vec<int> result;
vec<int> deleted(graph.size(), false);
vec<int> in_count(graph.size());
rep(i, graph.size()) {
for (auto next : graph[i]) {
in_count[next]++;
}
}
queue<int> q;
rep(i, graph.size()) {
if (in_count[i] == 0) {
q.push(i);
}
}
while (!q.empty()) {
int now = q.front();
q.pop();
result.emplace_back(now);
deleted[now] = true;
for (auto next : graph[now]) {
if (deleted[next])
continue;
in_count[next]--;
if (in_count[next] == 0) {
q.push(next);
}
}
}
return result;
}
#line 2 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/math/all.hpp"
// #include "combination.hpp"
// #include "factorial.hpp"
#line 2 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/math/modint.hpp"
#line 5 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/math/modint.hpp"
namespace modint_utils {
constexpr inline int32_t normalize(int val, int32_t mod) {
return (val % mod + mod) % mod;
}
constexpr inline int32_t inv(int32_t a, int32_t mod) {
int32_t b = mod, u = 1, v = 0;
while (b) {
int32_t t = a / b;
a -= t * b;
swap(a, b);
u -= t * v;
swap(u, v);
}
u %= mod;
if (u < 0)
u += mod;
return u;
// return mod_pow(val, mod - 2, mod);
}
} // namespace modint_utils
template <int MOD> struct dynamic_modint {
private:
int _val;
public:
dynamic_modint() : dynamic_modint(0) {}
dynamic_modint(int val) : _val(modint_utils::normalize(val, MOD)) {}
// logic
int val() const { return _val; }
inline dynamic_modint inv() const {
return dynamic_modint(modint_utils::inv(_val, MOD));
}
inline dynamic_modint pow(const int n) const {
return dynamic_modint(powm(_val, n, MOD));
}
inline static constexpr dynamic_modint pow(const dynamic_modint &a,
const int n) {
return dynamic_modint(mod_pow(a._val, n, a.MOD));
}
// op
inline dynamic_modint &operator++() { return *this += 1; }
inline dynamic_modint &operator--() { return *this -= 1; }
inline dynamic_modint operator++(int32_t) const {
dynamic_modint tmp = *this;
++*this;
return tmp;
}
inline dynamic_modint operator--(int32_t) {
dynamic_modint tmp = *this;
--*this;
return tmp;
}
inline dynamic_modint operator+(const dynamic_modint &a) const {
return dynamic_modint(_val) += a;
}
inline dynamic_modint operator-(const dynamic_modint &a) const {
return dynamic_modint(_val) -= a;
}
inline dynamic_modint operator*(const dynamic_modint &a) const {
return dynamic_modint(_val) *= a;
}
inline dynamic_modint operator/(const dynamic_modint &a) const {
return dynamic_modint(_val) /= a;
}
inline bool operator==(const dynamic_modint &a) { return _val == a._val; }
inline bool operator!=(const dynamic_modint &a) { return _val != a._val; }
inline dynamic_modint &operator+=(const dynamic_modint &a) {
_val += a.val();
if (_val >= MOD)
_val -= MOD;
return *this;
}
inline dynamic_modint &operator-=(const dynamic_modint &a) {
_val -= a.val();
if (_val < 0)
_val += MOD;
return *this;
}
inline dynamic_modint &operator*=(const dynamic_modint &a) {
_val = _val * a.val() % MOD;
return *this;
}
inline dynamic_modint &operator/=(const dynamic_modint &a) {
*this *= modint_utils::inv(a.val(), MOD);
return *this;
}
explicit operator int() const { return _val; }
// io
friend ostream &operator<<(ostream &os, const dynamic_modint &a) {
return os << a._val;
}
friend istream &operator>>(istream &os, dynamic_modint &a) {
os >> a._val;
a._val = modint_utils::normalize(a._val, MOD);
return os;
}
};
// using modint998 = modint<998244353>;
template <int MOD>
ostream &operator<<(ostream &os, const dynamic_modint<MOD> &i) {
os << i.val();
return os;
}
template <int MOD>
ostream &operator<<(ostream &os, const vector<dynamic_modint<MOD>> &v) {
for (int i = 0; i < (int)v.size(); i++) {
os << v[i].val() << (i + 1 != (int)v.size() ? " " : "");
}
return os;
}
template <const int32_t MOD> struct modint {
private:
using i32 = int32_t;
i32 _val;
public:
consteval inline modint() noexcept : _val(0) {}
constexpr inline modint(int val) noexcept
: _val(modint_utils::normalize(val, MOD)) {}
constexpr inline modint(modint const &val) noexcept : _val(val._val) {}
// logic
constexpr i32 val() const noexcept { return _val; }
constexpr modint pow(const int n) const { return modint(powm(_val, n, MOD)); }
constexpr inline static modint pow(const modint &a, const int n) noexcept {
return modint(mod_pow(a._val, n, a.MOD));
}
constexpr inline modint inv() const noexcept {
return modint(modint_utils::inv(_val, MOD));
}
// op
constexpr inline modint &operator++() noexcept { return *this += 1; }
constexpr inline modint &operator--() noexcept { return *this -= 1; }
constexpr inline modint operator++(int32_t) noexcept {
modint tmp = *this;
++*this;
return tmp;
}
constexpr inline modint operator--(int32_t) noexcept {
modint tmp = *this;
--*this;
return tmp;
}
constexpr inline modint operator+(const modint &a) const noexcept {
return modint(*this) += a;
}
constexpr inline modint operator-(const modint &a) const noexcept {
return modint(*this) -= a;
}
constexpr inline modint operator*(const modint &a) const noexcept {
return modint(*this) *= a;
}
constexpr inline modint operator/(const modint &a) const noexcept {
return modint(*this) /= a;
}
constexpr inline bool operator==(const modint &a) const noexcept {
return _val == a.val();
}
constexpr inline bool operator!=(const modint &a) const noexcept {
return _val != a.val();
}
constexpr inline modint &operator+=(const modint &a) noexcept {
_val += a._val;
if (_val >= MOD)
_val -= MOD;
return *this;
}
constexpr inline modint &operator-=(const modint &a) noexcept {
_val -= a._val;
if (_val < 0)
_val += MOD;
return *this;
}
constexpr inline modint &operator*=(const modint &a) noexcept {
_val = (ll)_val * a._val % MOD;
return *this;
}
constexpr inline modint &operator/=(const modint &a) noexcept {
*this *= modint_utils::inv(a.val(), MOD);
return *this;
}
explicit operator int() const noexcept { return _val; }
// io
friend ostream &operator<<(ostream &os, const modint &a) noexcept {
return os << a._val;
}
friend istream &operator>>(istream &os, modint &a) noexcept {
os >> a._val;
a._val = modint_utils::normalize(a._val, MOD);
return os;
}
};
using mint998 = modint<998244353>;
#line 2 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/math/prime.hpp"
#line 5 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/math/prime.hpp"
// ミラーラビン素数判定法
// O(k log^3 n)
// https://drken1215.hatenablog.com/entry/2023/05/23/233000
bool MillerRabin(long long N, vector<long long> A) {
long long s = 0, d = N - 1;
while (d % 2 == 0) {
++s;
d >>= 1;
}
for (auto a : A) {
if (N <= a)
return true;
long long t, x = powm(a, d, N);
if (x != 1) {
for (t = 0; t < s; ++t) {
if (x == N - 1)
break;
x = __int128_t(x) * x % N;
}
if (t == s)
return false;
}
}
return true;
}
bool is_prime(long long N) {
if (N <= 1)
return false;
if (N == 2)
return true;
if (N % 2 == 0)
return false;
if (N < 4759123141LL)
return MillerRabin(N, {2, 7, 61});
else
return MillerRabin(N, {2, 325, 9375, 28178, 450775, 9780504, 1795265022});
}
// ポラード・ロー素因数分解法
// 値が大きい場合に有効、ちゃんと調べる!
// O(n^(1/4))
// https://lpha-z.hatenablog.com/entry/2023/01/15/231500
// https://algo-method.com/tasks/553/editorial
uint64_t pollard_rho(uint64_t N) {
if (N % 2 == 0)
return 2;
if (is_prime(N))
return N;
uint64_t step = 0;
auto f = [&](uint64_t x) -> uint64_t {
return (__int128_t(x) * x + step) % N;
};
while (true) {
++step;
uint64_t x = step, y = f(x);
while (true) {
uint64_t p = gcd(y - x + N, N);
if (p == 0 || p == N)
break;
if (p != 1)
return p;
x = f(x);
y = f(f(y));
}
}
}
// 素因数分解
// https://algo-method.com/tasks/553/editorial
struct PrimeFactor {
uint64_t prime;
uint64_t exp;
};
vec<PrimeFactor> prime_factorize(uint64_t N) {
if (N == 1)
return {};
uint64_t p = pollard_rho(N);
if (p == N)
return {{p, 1}};
auto left = prime_factorize(p);
auto right = prime_factorize(N / p);
left.insert(left.end(), all(right));
sort(all(left), [](const PrimeFactor &a, const PrimeFactor &b) {
return a.prime < b.prime;
});
vec<PrimeFactor> ans;
rep(i, left.size()) {
if (i == 0 || left[i].prime != left[i - 1].prime)
ans.emplace_back(left[i]);
else
ans.back().exp += left[i].exp;
}
return ans;
}
#line 2 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/math/rational.hpp"
template <typename T = ll> struct Rational {
T num, den;
Rational(T num) : num(num), den(1) {}
Rational(T num, T den) : num(num), den(den) {
T g = gcd(num, den);
this->num /= g;
this->den /= g;
}
Rational operator+(const Rational &rhs) const {
return Rational(num * rhs.den + rhs.num * den, den * rhs.den);
}
Rational operator-(const Rational &rhs) const {
return Rational(num * rhs.den - rhs.num * den, den * rhs.den);
}
Rational operator*(const Rational &rhs) const {
return Rational(num * rhs.num, den * rhs.den);
}
Rational operator/(const Rational &rhs) const {
return Rational(num * rhs.den, den * rhs.num);
}
bool operator<(const Rational &rhs) const {
return num * rhs.den < rhs.num * den;
}
bool operator>(const Rational &rhs) const {
return num * rhs.den > rhs.num * den;
}
bool operator==(const Rational &rhs) const {
return num * rhs.den == rhs.num * den;
}
bool operator!=(const Rational &rhs) const { return !(*this == rhs); }
bool operator<=(const Rational &rhs) const {
return (*this < rhs) || (*this == rhs);
}
bool operator>=(const Rational &rhs) const {
return (*this > rhs) || (*this == rhs);
}
friend ostream &operator<<(ostream &os, const Rational &r) {
return os << r.num << "/" << r.den;
}
void operator+=(const Rational &rhs) { *this = *this + rhs; }
void operator-=(const Rational &rhs) { *this = *this - rhs; }
void operator*=(const Rational &rhs) { *this = *this * rhs; }
void operator/=(const Rational &rhs) { *this = *this / rhs; }
double val() const { return (double)num / den; }
// operator double() const { return val(); }
// operator string() const { return to_string(num) + "/" + to_string(den); }
Rational pow(ll n) const {
if (n == 0) {
return Rational(1);
} else if (n < 0) {
return Rational(den, num).pow(-n);
} else {
Rational res = pow(n / 2);
res *= res;
if (n % 2 == 1) {
res *= *this;
}
return res;
}
}
};
#line 9 "/home/zoi/ghq/github.com/ZOI-dayo/atcoder-library/all.hpp"
// #include "string/all.hpp"
// #include "util/all.hpp"
#line 3 "main.cpp"
using mint = modint<998'244'353>;
using cpp_int = boost::multiprecision::cpp_int;
void solve() {
int N, M, X;
cin >> N >> M >> X;
vvec<pair<int, int>> g(N);
rep(i, M) {
int u, v, c, t;
cin >> u >> v >> c >> t;
u--; v--;
g[u].emplace_back(v, t*X + c);
g[v].emplace_back(u, t*X + c);
}
vec<int> way(N, -1);
rp_queue<pair<int, int>> q;
q.push({0, 0});
way[0] = 0;
while (!q.empty()) {
auto [cost, loc] = q.top();
q.pop();
if(loc == N - 1) break;
for (auto &next : g[loc]) {
int next_cost = cost + next.sec;
if (way[next.fir] >= 0 && way[next.fir] <= next_cost)
continue;
way[next.fir] = next_cost;
q.push({way[next.fir], next.fir});
}
}
// printd(way[N - 1]);
cpp_int ans = bin_search<cpp_int>(-2, INF, [&](cpp_int x) {
// printd(x);
// printd(way[N - 1]);
// printd(x * X);
return x < 0 || way[N - 1] > x * X;
});
if(ans < 0) {
cout << -1 << endl;
} else {
cout << ans+1 << endl;
}
}
void test() {
}
signed main() {
io_setup();
// input
solve();
// test();
}