結果
問題 | No.631 Noelちゃんと電車旅行 |
ユーザー | yuruhiya |
提出日時 | 2021-04-02 16:54:44 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 67 ms / 2,000 ms |
コード長 | 24,811 bytes |
コンパイル時間 | 2,752 ms |
コンパイル使用メモリ | 209,076 KB |
実行使用メモリ | 7,040 KB |
最終ジャッジ日時 | 2024-10-02 09:50:18 |
合計ジャッジ時間 | 5,422 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 41 ms
6,812 KB |
testcase_01 | AC | 67 ms
7,040 KB |
testcase_02 | AC | 65 ms
7,040 KB |
testcase_03 | AC | 64 ms
7,040 KB |
testcase_04 | AC | 63 ms
7,040 KB |
testcase_05 | AC | 63 ms
7,040 KB |
testcase_06 | AC | 25 ms
6,816 KB |
testcase_07 | AC | 14 ms
6,816 KB |
testcase_08 | AC | 48 ms
6,912 KB |
testcase_09 | AC | 52 ms
6,820 KB |
testcase_10 | AC | 39 ms
6,912 KB |
testcase_11 | AC | 33 ms
6,816 KB |
testcase_12 | AC | 43 ms
6,912 KB |
testcase_13 | AC | 39 ms
6,820 KB |
testcase_14 | AC | 18 ms
6,820 KB |
testcase_15 | AC | 34 ms
6,816 KB |
testcase_16 | AC | 2 ms
6,820 KB |
testcase_17 | AC | 2 ms
6,820 KB |
testcase_18 | AC | 2 ms
6,820 KB |
testcase_19 | AC | 2 ms
6,816 KB |
testcase_20 | AC | 2 ms
6,824 KB |
ソースコード
#line 2 "/home/yuruhiya/programming/library/Utility/get_MOD.cpp" constexpr long long get_MOD() { #ifdef SET_MOD return SET_MOD; #else return 1000000007; #endif } #line 3 "/home/yuruhiya/programming/library/Utility/constants.cpp" #include <vector> #include <string> #include <utility> #include <queue> #define rep(i, n) for (int i = 0; i < (n); ++i) #define FOR(i, m, n) for (int i = (m); i < (n); ++i) #define rrep(i, n) for (int i = (n)-1; i >= 0; --i) #define rfor(i, m, n) for (int i = (m); i >= (n); --i) #define loop(n) rep(i##__COUNTER__, n) #define unless(c) if (!(c)) #define ALL(x) (x).begin(), (x).end() #define RALL(x) (x).rbegin(), (x).rend() #define range_it(a, l, r) (a).begin() + (l), (a).begin() + (r) using ll = long long; using LD = long double; using VB = std::vector<bool>; using VVB = std::vector<VB>; using VI = std::vector<int>; using VVI = std::vector<VI>; using VL = std::vector<ll>; using VVL = std::vector<VL>; using VS = std::vector<std::string>; using VD = std::vector<LD>; using PII = std::pair<int, int>; using VP = std::vector<PII>; using PLL = std::pair<ll, ll>; using VPL = std::vector<PLL>; template <class T> using PQ = std::priority_queue<T>; template <class T> using PQS = std::priority_queue<T, std::vector<T>, std::greater<T>>; constexpr int inf = 1000000000; constexpr long long inf_ll = 1000000000000000000ll, MOD = get_MOD(); constexpr long double PI = 3.14159265358979323846, EPS = 1e-12; #line 2 "/home/yuruhiya/programming/library/Utility/Scanner.cpp" #include <iostream> #line 6 "/home/yuruhiya/programming/library/Utility/Scanner.cpp" #include <tuple> #include <type_traits> #ifdef _WIN32 #define getchar_unlocked _getchar_nolock #define putchar_unlocked _putchar_nolock #define fwrite_unlocked fwrite #define fflush_unlocked fflush #endif class Scanner { static int gc() { return getchar_unlocked(); } static char next_char() { char c; scan(c); return c; } template <class T> static void scan(T& v) { std::cin >> v; } static void scan(char& v) { while (std::isspace(v = gc())) ; } static void scan(bool& v) { v = next_char() != '0'; } static void scan(std::vector<bool>::reference v) { bool b; scan(b); v = b; } static void scan(std::string& v) { v.clear(); for (char c = next_char(); !std::isspace(c); c = gc()) v += c; } static void scan(int& v) { v = 0; bool neg = false; char c = next_char(); if (c == '-') { neg = true; c = gc(); } for (; std::isdigit(c); c = gc()) v = v * 10 + (c - '0'); if (neg) v = -v; } static void scan(long long& v) { v = 0; bool neg = false; char c = next_char(); if (c == '-') { neg = true; c = gc(); } for (; std::isdigit(c); c = gc()) v = v * 10 + (c - '0'); if (neg) v = -v; } static void scan(double& v) { v = 0; double dp = 1; bool neg = false, after_dp = false; char c = next_char(); if (c == '-') { neg = true; c = gc(); } for (; std::isdigit(c) || c == '.'; c = gc()) { if (c == '.') { after_dp = true; } else if (after_dp) { v += (c - '0') * (dp *= 0.1); } else { v = v * 10 + (c - '0'); } } if (neg) v = -v; } static void scan(long double& v) { v = 0; long double dp = 1; bool neg = false, after_dp = false; char c = next_char(); if (c == '-') { neg = true; c = gc(); } for (; std::isdigit(c) || c == '.'; c = gc()) { if (c == '.') { after_dp = true; } else if (after_dp) { v += (c - '0') * (dp *= 0.1); } else { v = v * 10 + (c - '0'); } } if (neg) v = -v; } template <class T, class U> static void scan(std::pair<T, U>& v) { scan(v.first); scan(v.second); } template <class T, std::enable_if_t<!std::is_same_v<bool, T>, std::nullptr_t> = nullptr> static void scan(std::vector<T>& v) { for (auto& e : v) scan(e); } template <class T, std::enable_if_t<std::is_same_v<bool, T>, std::nullptr_t> = nullptr> static void scan(std::vector<T>& v) { for (auto e : v) scan(e); } template <std::size_t N = 0, class T> static void scan_tuple_impl(T& v) { if constexpr (N < std::tuple_size_v<T>) { scan(std::get<N>(v)); scan_tuple_impl<N + 1>(v); } } template <class... T> static void scan(std::tuple<T...>& v) { scan_tuple_impl(v); } struct Read2DVectorHelper { std::size_t h, w; Read2DVectorHelper(std::size_t _h, std::size_t _w) : h(_h), w(_w) {} template <class T> operator std::vector<std::vector<T>>() { std::vector vector(h, std::vector<T>(w)); scan(vector); return vector; } }; struct ReadVectorHelper { std::size_t n; ReadVectorHelper(std::size_t _n) : n(_n) {} template <class T> operator std::vector<T>() { std::vector<T> vector(n); scan(vector); return vector; } auto operator[](std::size_t m) { return Read2DVectorHelper(n, m); } }; public: template <class T> T read() const { T result; scan(result); return result; } template <class T> auto read(std::size_t n) const { std::vector<T> result(n); scan(result); return result; } template <class T> auto read(std::size_t h, std::size_t w) const { std::vector result(h, std::vector<T>(w)); scan(result); return result; } std::string read_line() const { std::string v; for (char c = gc(); c != '\n' && c != '\0'; c = gc()) v += c; return v; } template <class T> operator T() const { return read<T>(); } int operator--(int) const { return read<int>() - 1; } auto operator[](std::size_t n) const { return ReadVectorHelper(n); } auto operator[](const std::pair<std::size_t, std::size_t>& nm) const { return Read2DVectorHelper(nm.first, nm.second); } void operator()() const {} template <class H, class... T> void operator()(H&& h, T&&... t) const { scan(h); operator()(std::forward<T>(t)...); } private: template <template <class...> class, class...> struct Column; template <template <class...> class V, class Head, class... Tail> struct Column<V, Head, Tail...> { template <class... Args> using vec = V<std::vector<Head>, Args...>; using type = typename Column<vec, Tail...>::type; }; template <template <class...> class V> struct Column<V> { using type = V<>; }; template <class... T> using column_t = typename Column<std::tuple, T...>::type; template <std::size_t N = 0, class T> void column_impl(T& t) const { if constexpr (N < std::tuple_size_v<T>) { auto& vec = std::get<N>(t); using V = typename std::remove_reference_t<decltype(vec)>::value_type; vec.push_back(read<V>()); column_impl<N + 1>(t); } } public: template <class... T> auto column(std::size_t h) const { column_t<T...> result; while (h--) column_impl(result); return result; } } in; #define inputs(T, ...) \ T __VA_ARGS__; \ in(__VA_ARGS__) #define ini(...) inputs(int, __VA_ARGS__) #define inl(...) inputs(long long, __VA_ARGS__) #define ins(...) inputs(std::string, __VA_ARGS__) #line 5 "/home/yuruhiya/programming/library/Utility/Printer.cpp" #include <array> #line 7 "/home/yuruhiya/programming/library/Utility/Printer.cpp" #include <string_view> #include <optional> #include <charconv> #include <cstring> #include <cassert> class Printer { public: struct BoolString { std::string_view t, f; BoolString(std::string_view _t, std::string_view _f) : t(_t), f(_f) {} }; struct Separator { std::string_view div, sep, last; Separator(std::string_view _div, std::string_view _sep, std::string_view _last) : div(_div), sep(_sep), last(_last) {} }; inline static const BoolString Yes{"Yes", "No"}, yes{"yes", "no"}, YES{"YES", "NO"}, Int{"1", "0"}, Possible{"Possible", "Impossible"}; inline static const Separator space{" ", " ", "\n"}, no_space{"", "", "\n"}, endl{"\n", "\n", "\n"}, comma{",", ",", "\n"}, no_endl{" ", " ", ""}, sep_endl{" ", "\n", "\n"}; BoolString bool_str{Yes}; Separator separator{space}; void print(int v) const { char buf[12]{}; if (auto [ptr, e] = std::to_chars(std::begin(buf), std::end(buf), v); e == std::errc{}) { print(std::string_view(buf, ptr - buf)); } else { assert(false); } } void print(long long v) const { char buf[21]{}; if (auto [ptr, e] = std::to_chars(std::begin(buf), std::end(buf), v); e == std::errc{}) { print(std::string_view(buf, ptr - buf)); } else { assert(false); } } void print(bool v) const { print(v ? bool_str.t : bool_str.f); } void print(std::vector<bool>::reference v) const { print(v ? bool_str.t : bool_str.f); } void print(char v) const { putchar_unlocked(v); } void print(std::string_view v) const { fwrite_unlocked(v.data(), sizeof(std::string_view::value_type), v.size(), stdout); } void print(double v) const { std::printf("%.20f", v); } void print(long double v) const { std::printf("%.20Lf", v); } template <class T> void print(const T& v) const { std::cout << v; } template <class T, class U> void print(const std::pair<T, U>& v) const { print(v.first); print(separator.div); print(v.second); } template <class T> void print(const std::optional<T>& v) const { print(*v); } template <class InputIterater> void print_range(const InputIterater& begin, const InputIterater& end) const { for (InputIterater i = begin; i != end; ++i) { if (i != begin) print(separator.sep); print(*i); } } template <class T> void print(const std::vector<T>& v) const { print_range(v.begin(), v.end()); } template <class T, std::size_t N> void print(const std::array<T, N>& v) const { print_range(v.begin(), v.end()); } template <class T> void print(const std::vector<std::vector<T>>& v) const { for (std::size_t i = 0; i < v.size(); ++i) { if (i) print(separator.last); print(v[i]); } } Printer() = default; Printer(const BoolString& _bool_str, const Separator& _separator) : bool_str(_bool_str), separator(_separator) {} Printer& operator()() { print(separator.last); return *this; } template <class Head> Printer& operator()(Head&& head) { print(head); print(separator.last); return *this; } template <class Head, class... Tail> Printer& operator()(Head&& head, Tail&&... tail) { print(head); print(separator.sep); return operator()(std::forward<Tail>(tail)...); } template <class... Args> Printer& flag(bool f, Args&&... args) { if (f) { return operator()(std::forward<Args>(args)...); } else { return *this; } } template <class InputIterator> Printer& range(const InputIterator& begin, const InputIterator& end) { print_range(begin, end); print(separator.last); return *this; } template <class Container> Printer& range(const Container& a) { range(a.begin(), a.end()); return *this; } template <class... T> void exit(T&&... t) { operator()(std::forward<T>(t)...); std::exit(EXIT_SUCCESS); } Printer& flush() { fflush_unlocked(stdout); return *this; } Printer& set(const BoolString& _bool_str) { bool_str = _bool_str; return *this; } Printer& set(const Separator& _separator) { separator = _separator; return *this; } Printer& set(std::string_view t, std::string_view f) { bool_str = BoolString(t, f); return *this; } } out; #line 2 "/home/yuruhiya/programming/library/Utility/functions.cpp" #include <algorithm> #include <numeric> #include <cmath> #line 8 "/home/yuruhiya/programming/library/Utility/functions.cpp" template <class T = long long> constexpr T TEN(std::size_t n) { T result = 1; for (std::size_t i = 0; i < n; ++i) result *= 10; return result; } template < class T, class U, std::enable_if_t<std::is_integral_v<T> && std::is_integral_v<U>, std::nullptr_t> = nullptr> constexpr auto div_ceil(T n, U m) { return (n + m - 1) / m; } template <class T, class U> constexpr auto div_ceil2(T n, U m) { return div_ceil(n, m) * m; } template <class T> constexpr T triangle(T n) { return (n & 1) ? (n + 1) / 2 * n : n / 2 * (n + 1); } template <class T> constexpr T nC2(T n) { return (n & 1) ? (n - 1) / 2 * n : n / 2 * (n - 1); } template <class T, class U> constexpr auto middle(const T& l, const U& r) { return l + (r - l) / 2; } template <class T, class U, class V> constexpr bool in_range(const T& v, const U& lower, const V& upper) { return lower <= v && v < upper; } template <class T, std::enable_if_t<std::is_integral_v<T>, std::nullptr_t> = nullptr> constexpr bool is_square(T n) { T s = std::sqrt(n); return s * s == n || (s + 1) * (s + 1) == n; } template <class T = long long> constexpr T BIT(int b) { return T(1) << b; } template <class T> constexpr int BIT(T x, int i) { return (x & (T(1) << i)) ? 1 : 0; } template <class T> constexpr int Sgn(T x) { return (0 < x) - (0 > x); } template <class T> bool is_leap(T year) { return !(year % 4) && (year % 100 || !(year % 400)); } template <class T, class U, std::enable_if_t<std::is_integral_v<U>, std::nullptr_t> = nullptr> constexpr T Pow(T a, U n) { assert(n >= 0); T result = 1; while (n > 0) { if (n & 1) { result *= a; n--; } else { a *= a; n >>= 1; } } return result; } template <class T, class U, std::enable_if_t<std::is_integral_v<U>, std::nullptr_t> = nullptr> constexpr T Powmod(T a, U n, T mod) { assert(n >= 0); if (a > mod) a %= mod; T result = 1; while (n > 0) { if (n & 1) { result = result * a % mod; n--; } else { a = a * a % mod; n >>= 1; } } return result; } template <class T> bool chmax(T& a, const T& b) { return a < b ? a = b, true : false; } template <class T> bool chmin(T& a, const T& b) { return a > b ? a = b, true : false; } template <class T> int sz(const T& v) { return v.size(); } template <class T, class U> int lower_index(const T& a, const U& v) { return std::lower_bound(a.begin(), a.end(), v) - a.begin(); } template <class T, class U> int upper_index(const T& a, const U& v) { return std::upper_bound(a.begin(), a.end(), v) - a.begin(); } template <class T, class U = typename T::value_type> U Gcdv(const T& v) { return std::accumulate(std::next(v.begin()), v.end(), U(*v.begin()), std::gcd<U, U>); } template <class T, class U = typename T::value_type> U Lcmv(const T& v) { return std::accumulate(std::next(v.begin()), v.end(), U(*v.begin()), std::lcm<U, U>); } namespace internal { template <class T, std::size_t N> auto make_vector(std::vector<int>& sizes, const T& init) { if constexpr (N == 1) { return std::vector(sizes[0], init); } else { int size = sizes[N - 1]; sizes.pop_back(); return std::vector(size, make_vector<T, N - 1>(sizes, init)); } } } // namespace internal template <class T, std::size_t N> auto make_vector(const int (&sizes)[N], const T& init = T()) { std::vector s(std::rbegin(sizes), std::rend(sizes)); return internal::make_vector<T, N>(s, init); } namespace lambda { auto char_to_int = [](char c) { return c - '0'; }; auto lower_to_int = [](char c) { return c - 'a'; }; auto upper_to_int = [](char c) { return c - 'A'; }; auto int_to_char = [](int i) -> char { return '0' + i; }; auto int_to_lower = [](int i) -> char { return 'a' + i; }; auto int_to_upper = [](int i) -> char { return 'A' + i; }; auto is_odd = [](auto n) { return n % 2 == 1; }; auto is_even = [](auto n) { return n % 2 == 0; }; auto is_positive = [](auto n) { return n > 0; }; auto is_negative = [](auto n) { return n < 0; }; auto increment = [](auto n) { return ++n; }; auto decrement = [](auto n) { return --n; }; auto self = [](const auto& n) { return n; }; auto first = [](const auto& n) { return n.first; }; auto second = [](const auto& n) { return n.second; }; template <class T> auto cast() { return [](const auto& n) { return static_cast<T>(n); }; }; template <class T> auto equal_to(const T& x) { return [x](auto y) { return x == y; }; } template <std::size_t I> auto get() { return [](const auto& n) { return std::get<I>(n); }; } template <class F> auto cmp(F&& f) { return [f](const auto& a, const auto& b) { return f(a) < f(b); }; } } // namespace lambda #line 6 "/home/yuruhiya/programming/library/template_no_Ruby.cpp" #if __has_include(<library/dump.hpp>) #include <library/dump.hpp> #define LOCAL #else #define dump(...) ((void)0) #define dump2(...) ((void)0) #endif #line 2 "/home/yuruhiya/programming/library/Utility/oj_local.cpp" template <class T> constexpr T oj_local(const T& oj, const T& local) { #ifndef LOCAL return oj; #else return local; #endif } #line 14 "/home/yuruhiya/programming/library/template_no_Ruby.cpp" #include <bits/stdc++.h> #line 1 "/home/yuruhiya/programming/library/atcoder/lazysegtree.hpp" #line 1 "/home/yuruhiya/programming/library/atcoder/internal_bit.hpp" #ifdef _MSC_VER #include <intrin.h> #endif namespace atcoder { namespace internal { // @param n `0 <= n` // @return minimum non-negative `x` s.t. `n <= 2**x` int ceil_pow2(int n) { int x = 0; while ((1U << x) < (unsigned int)(n)) x++; return x; } // @param n `1 <= n` // @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0` int bsf(unsigned int n) { #ifdef _MSC_VER unsigned long index; _BitScanForward(&index, n); return index; #else return __builtin_ctz(n); #endif } } // namespace internal } // namespace atcoder #line 9 "/home/yuruhiya/programming/library/atcoder/lazysegtree.hpp" namespace atcoder { template <class S, S (*op)(S, S), S (*e)(), class F, S (*mapping)(F, S), F (*composition)(F, F), F (*id)()> struct lazy_segtree { public: lazy_segtree() : lazy_segtree(0) {} lazy_segtree(int n) : lazy_segtree(std::vector<S>(n, e())) {} lazy_segtree(const std::vector<S>& v) : _n(int(v.size())) { log = internal::ceil_pow2(_n); size = 1 << log; d = std::vector<S>(2 * size, e()); lz = std::vector<F>(size, id()); for (int i = 0; i < _n; i++) d[size + i] = v[i]; for (int i = size - 1; i >= 1; i--) { update(i); } } void set(int p, S x) { assert(0 <= p && p < _n); p += size; for (int i = log; i >= 1; i--) push(p >> i); d[p] = x; for (int i = 1; i <= log; i++) update(p >> i); } S get(int p) { assert(0 <= p && p < _n); p += size; for (int i = log; i >= 1; i--) push(p >> i); return d[p]; } S operator[](int p) { return get(p); } S prod(int l, int r) { assert(0 <= l && l <= r && r <= _n); if (l == r) return e(); l += size; r += size; for (int i = log; i >= 1; i--) { if (((l >> i) << i) != l) push(l >> i); if (((r >> i) << i) != r) push(r >> i); } S sml = e(), smr = e(); while (l < r) { if (l & 1) sml = op(sml, d[l++]); if (r & 1) smr = op(d[--r], smr); l >>= 1; r >>= 1; } return op(sml, smr); } S operator()(int l, int r) { return prod(l, r); } S all_prod() { return d[1]; } void apply(int p, F f) { assert(0 <= p && p < _n); p += size; for (int i = log; i >= 1; i--) push(p >> i); d[p] = mapping(f, d[p]); for (int i = 1; i <= log; i++) update(p >> i); } void apply(int l, int r, F f) { assert(0 <= l && l <= r && r <= _n); if (l == r) return; l += size; r += size; for (int i = log; i >= 1; i--) { if (((l >> i) << i) != l) push(l >> i); if (((r >> i) << i) != r) push((r - 1) >> i); } { int l2 = l, r2 = r; while (l < r) { if (l & 1) all_apply(l++, f); if (r & 1) all_apply(--r, f); l >>= 1; r >>= 1; } l = l2; r = r2; } for (int i = 1; i <= log; i++) { if (((l >> i) << i) != l) update(l >> i); if (((r >> i) << i) != r) update((r - 1) >> i); } } template <bool (*g)(S)> int max_right(int l) { return max_right(l, [](S x) { return g(x); }); } template <class G> int max_right(int l, G g) { assert(0 <= l && l <= _n); assert(g(e())); if (l == _n) return _n; l += size; for (int i = log; i >= 1; i--) push(l >> i); S sm = e(); do { while (l % 2 == 0) l >>= 1; if (!g(op(sm, d[l]))) { while (l < size) { push(l); l = (2 * l); if (g(op(sm, d[l]))) { sm = op(sm, d[l]); l++; } } return l - size; } sm = op(sm, d[l]); l++; } while ((l & -l) != l); return _n; } template <bool (*g)(S)> int min_left(int r) { return min_left(r, [](S x) { return g(x); }); } template <class G> int min_left(int r, G g) { assert(0 <= r && r <= _n); assert(g(e())); if (r == 0) return 0; r += size; for (int i = log; i >= 1; i--) push((r - 1) >> i); S sm = e(); do { r--; while (r > 1 && (r % 2)) r >>= 1; if (!g(op(d[r], sm))) { while (r < size) { push(r); r = (2 * r + 1); if (g(op(d[r], sm))) { sm = op(d[r], sm); r--; } } return r + 1 - size; } sm = op(d[r], sm); } while ((r & -r) != r); return 0; } std::vector<S> to_a() { std::vector<S> res(_n); for (int i = 0; i < _n; ++i) { res[i] = get(i); } return res; } private: int _n, size, log; std::vector<S> d; std::vector<F> lz; void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); } void all_apply(int k, F f) { d[k] = mapping(f, d[k]); if (k < size) lz[k] = composition(f, lz[k]); } void push(int k) { all_apply(2 * k, lz[k]); all_apply(2 * k + 1, lz[k]); lz[k] = id(); } }; } // namespace atcoder #line 5 "/home/yuruhiya/programming/library/DataStructure/LazySegmentTree.cpp" namespace internal { template <class T> struct S_sum { T value, size; S_sum(T v, T s = 1) : value(v), size(s) {} }; template <class S> constexpr S constant_min() { return std::numeric_limits<S>::min(); } template <class S> constexpr S constant_max() { return std::numeric_limits<S>::max(); } template <class S> constexpr S constant_zero() { return static_cast<S>(0); } template <class T> constexpr S_sum<T> constant_zero_sum() { return {0, 0}; } template <class S> constexpr S op_max(S x, S y) { return std::max(x, y); } template <class S> constexpr S op_min(S x, S y) { return std::min(x, y); } template <class T> constexpr S_sum<T> op_sum(S_sum<T> x, S_sum<T> y) { return {x.value + y.value, x.size + y.size}; } template <class S, class F> constexpr S mapping_add(F f, S x) { return f + x; } template <class T, class F> constexpr S_sum<T> mapping_add_sum(F f, S_sum<T> x) { return {x.value + f * x.size, x.size}; } template <class S, class F> constexpr S mapping_update(F f, S x) { return f == constant_max<F>() ? x : f; } template <class T, class F> constexpr S_sum<T> mapping_update_sum(F f, S_sum<T> x) { if (f != constant_max<F>()) x.value = f * x.size; return x; } template <class F> constexpr F composition_add(F f, F g) { return f + g; } template <class F> constexpr F composition_update(F f, F g) { return f == constant_max<F>() ? g : f; } } // namespace internal using internal::S_sum; template <class S, class F> using RangeAddRangeMax = atcoder::lazy_segtree<S, internal::op_max<S>, internal::constant_min<S>, F, internal::mapping_add<S, F>, internal::composition_add<F>, internal::constant_zero<F>>; template <class S, class F> using RangeAddRangeMin = atcoder::lazy_segtree<S, internal::op_min<S>, internal::constant_max<S>, F, internal::mapping_add<S, F>, internal::composition_add<F>, internal::constant_zero<F>>; template <class T, class F> using RangeAddRangeSum = atcoder::lazy_segtree<internal::S_sum<T>, internal::op_sum<T>, internal::constant_zero_sum<T>, F, internal::mapping_add_sum<T, F>, internal::composition_add<F>, internal::constant_zero<F>>; template <class S, class F> using RangeUpdateRangeMax = atcoder::lazy_segtree<S, internal::op_max<S>, internal::constant_min<S>, F, internal::mapping_update<S, F>, internal::composition_update<F>, internal::constant_max<F>>; template <class S, class F> using RangeUpdateRangeMin = atcoder::lazy_segtree<S, internal::op_min<S>, internal::constant_max<S>, F, internal::mapping_update<S, F>, internal::composition_update<F>, internal::constant_max<F>>; template <class T, class F> using RangeUpdateRangeSum = atcoder::lazy_segtree<internal::S_sum<T>, internal::op_sum<T>, internal::constant_zero_sum<T>, F, internal::mapping_update_sum<T, F>, internal::composition_update<F>, internal::constant_max<F>>; #line 3 "a.cpp" using namespace std; int main() { int n = in; VL t = in[n - 1]; rep(i, n - 1) t[i] += (n - i - 1) * 3; RangeAddRangeMax<ll, ll> seg(t); for (int m = in; m--;) { int l = in--, r = in; ll d = in; seg.apply(l, r, d); out(seg.all_prod()); } }