結果
| 問題 |
No.3319 Iwaijkstra
|
| コンテスト | |
| ユーザー |
 elphe
|
| 提出日時 | 2025-10-15 18:09:44 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 33,221 bytes |
| コンパイル時間 | 5,090 ms |
| コンパイル使用メモリ | 337,952 KB |
| 実行使用メモリ | 33,444 KB |
| 最終ジャッジ日時 | 2025-10-31 19:49:30 |
| 合計ジャッジ時間 | 17,141 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 16 WA * 3 TLE * 1 -- * 38 |
コンパイルメッセージ
In member function ‘constexpr uint_fast32_t MyLib::MinLazySegmentTree<T, Mapping, Composition, MinPicker, default_value>::leftest_below(uint_fast32_t, uint_fast32_t, T) [with T = unsigned int; Mapping = check(uint_fast32_t, uint_fast32_t, const std::vector<std::vector<std::array<unsigned int, 2> > >&)::<lambda(uint_least32_t, uint_least32_t, uint_fast32_t)>; Composition = check(uint_fast32_t, uint_fast32_t, const std::vector<std::vector<std::array<unsigned int, 2> > >&)::<lambda(uint_least32_t, uint_least32_t)>; MinPicker = MyLib::<lambda(unsigned int, unsigned int)>; T default_value = 4294967295]’,
inlined from ‘constexpr bool check(uint_fast32_t, uint_fast32_t, const std::vector<std::vector<std::array<unsigned int, 2> > >&)’ at main.cpp:621:53:
main.cpp:446:56: warning: ‘cur_index’ may be used uninitialized [-Wmaybe-uninitialized]
446 | --cur_layer, cur_index <<= 1;
| ~~~~~~~~~~^~~~~
main.cpp: In function ‘constexpr bool check(uint_fast32_t, uint_fast32_t, const std::vector<std::vector<std::array<unsigned int, 2> > >&)’:
main.cpp:382:50: note: ‘cur_index’ was declared here
382 | uint_fast32_t cur_layer, cur_index;
| ^~~~~~~~~
In member function ‘constexpr uint_fast32_t MyLib::MinLazySegmentTree<T, Mapping, Composition, MinPicker, default_value>::leftest_below(uint_fast32_t, uint_fast32_t, T) [with T = std::pair<long unsigned int, long unsigned int>; Mapping = solve(uint_fast32_t, const std::vector<std::vector<std::array<unsigned int, 3> > >&)::<lambda(const std::pair<long unsigned int, long unsigned int>&, const std::pair<long unsigned int, long unsigned int>&, uint_fast32_t)>; Composition = solve(uint_fast32_t, const std::vector<std::vector<std::array<unsigned int, 3> > >&)::<lambda(const std::pair<long unsigned int, long unsigned int>&, const std::pair<long unsigned int, lo
ソースコード
#include <bits/stdc++.h>
namespace MyLib
{
template<typename T, class Picker, T default_value> class LiteralSegmentTree
{
protected:
std::vector<std::vector<T>> containers;
public:
constexpr LiteralSegmentTree(const std::vector<T>& initializer)
{
containers.clear();
if (initializer.size() == 0) [[unlikely]] return;
else if (initializer.size() == 1) [[unlikely]] { containers.emplace_back(1, initializer[0]); return; }
uint_fast32_t l = 0, r = 30;
while (l + 1 < r)
{
const auto c = (l + r) >> 1;
if (((uint_fast32_t)1 << c) < initializer.size())
l = c;
else
r = c;
}
containers.emplace_back((uint_fast32_t)1 << r);
uint_fast32_t i;
for (i = 0; i != initializer.size(); ++i)
containers[0][i] = initializer[i];
for (; i != ((uint_fast32_t)1 << r); ++i)
containers[0][i] = default_value;
for (--r; r != 0; --r)
{
containers.emplace_back((uint_fast32_t)1 << r);
[[assume(containers.size() >= 2)]];
for (i = 0; i != ((uint_fast32_t)1 << r); ++i)
containers[containers.size() - 1][i] = Picker()(containers[containers.size() - 2][i << 1], containers[containers.size() - 2][(i << 1) | 1]);
}
containers.emplace_back(1, Picker()(containers[containers.size() - 1][0], containers[containers.size() - 1][1]));
}
constexpr LiteralSegmentTree(std::vector<T>&& initializer)
{
containers.clear();
if (initializer.size() == 0) [[unlikely]] return;
uint_fast32_t l = 0, r = 30;
while (l + 1 < r)
{
const auto c = (l + r) >> 1;
if (((uint_fast32_t)1 << c) < initializer.size())
l = c;
else
r = c;
}
containers.emplace_back(std::move(initializer));
containers[0].resize((uint_fast32_t)1 << r, default_value);
uint_fast32_t i;
for (--r; r != 0; --r)
{
containers.emplace_back((uint_fast32_t)1 << r);
[[assume(containers.size() >= 2)]];
for (i = 0; i != ((uint_fast32_t)1 << r); ++i)
containers[containers.size() - 1][i] = Picker()(containers[containers.size() - 2][i << 1], containers[containers.size() - 2][(i << 1) | 1]);
}
containers.emplace_back(1, Picker()(containers[containers.size() - 1][0], containers[containers.size() - 1][1]));
}
constexpr LiteralSegmentTree(const uint_fast32_t n) : LiteralSegmentTree<T, Picker, default_value>(std::vector<T>(n, default_value)) { }
constexpr LiteralSegmentTree(const uint_fast32_t n, const T initial_value) : LiteralSegmentTree<T, Picker, default_value>(std::vector<T>(n, initial_value)) { }
[[nodiscard]] constexpr T operator[](uint_fast32_t index) const noexcept { return containers[0][index]; }
[[nodiscard]] constexpr uint_fast32_t size() const noexcept { return containers[0].size(); }
[[nodiscard]] constexpr uint_fast32_t layer() const noexcept { return containers.size(); }
constexpr T update(uint_fast32_t index, const T value) noexcept
{
containers[0][index] = value;
index >>= 1;
for (uint_fast32_t i = 1; i != containers.size(); ++i, index >>= 1)
containers[i][index] = Picker()(containers[i - 1][index << 1], containers[i - 1][(index << 1) | 1]);
return value;
}
[[nodiscard]] constexpr T range_pick_up(uint_fast32_t first_index, uint_fast32_t end_index) const noexcept
{
if (containers.size() == 0 || end_index > containers[0].size()) [[unlikely]] return default_value;
T ret_l = default_value, ret_r = default_value;
for (uint_fast32_t cur_layer = 0; first_index < end_index; first_index >>= 1, end_index >>= 1, ++cur_layer)
{
if (first_index & 1)
ret_l = Picker()(ret_l, containers[cur_layer][first_index]), ++first_index;
if (end_index & 1)
ret_r = Picker()(containers[cur_layer][end_index - 1], ret_r);
}
return Picker()(ret_l, ret_r);
}
};
template<typename T, class Mapping, class Composition, class Picker, T default_value>
class LiteralLazySegmentTree : public LiteralSegmentTree<T, Picker, default_value>
{
protected:
std::vector<std::vector<std::pair<bool, T>>> unevaluated;
constexpr void convey_evaluation(const uint_fast32_t cur_layer, const uint_fast32_t cur_index) noexcept
{
[[assume(cur_layer >= 1)]];
if (unevaluated[cur_layer - 1][cur_index << 1].first)
unevaluated[cur_layer - 1][cur_index << 1].second = Composition()(unevaluated[cur_layer - 1][cur_index << 1].second, unevaluated[cur_layer][cur_index].second);
else
unevaluated[cur_layer - 1][cur_index << 1] = { true, unevaluated[cur_layer][cur_index].second };
if (unevaluated[cur_layer - 1][(cur_index << 1) | 1].first)
unevaluated[cur_layer - 1][(cur_index << 1) | 1].second = Composition()(unevaluated[cur_layer - 1][(cur_index << 1) | 1].second, unevaluated[cur_layer][cur_index].second);
else
unevaluated[cur_layer - 1][(cur_index << 1) | 1] = { true, unevaluated[cur_layer][cur_index].second };
unevaluated[cur_layer][cur_index] = { false, default_value };
}
constexpr void execute_evaluation_above(const uint_fast32_t first_index, const uint_fast32_t end_index) noexcept
{
for (uint_fast32_t cur_layer = unevaluated.size() - 1; (first_index & (((uint_fast32_t)1 << cur_layer) - 1)) != 0; --cur_layer)
if (unevaluated[cur_layer][first_index >> cur_layer].first)
{
this->containers[cur_layer][first_index >> cur_layer] = Mapping()(this->containers[cur_layer][first_index >> cur_layer], unevaluated[cur_layer][first_index >> cur_layer].second, (uint_fast32_t)1 << cur_layer);
convey_evaluation(cur_layer, first_index >> cur_layer);
}
for (uint_fast32_t cur_layer = unevaluated.size() - 1; (end_index & (((uint_fast32_t)1 << cur_layer) - 1)) != 0; --cur_layer)
if (unevaluated[cur_layer][(end_index - 1) >> cur_layer].first)
{
this->containers[cur_layer][(end_index - 1) >> cur_layer] = Mapping()(this->containers[cur_layer][(end_index - 1) >> cur_layer], unevaluated[cur_layer][(end_index - 1) >> cur_layer].second, (uint_fast32_t)1 << cur_layer);
convey_evaluation(cur_layer, (end_index - 1) >> cur_layer);
}
}
public:
constexpr LiteralLazySegmentTree(const std::vector<T>& initializer) : LiteralSegmentTree<T, Picker, default_value>(initializer)
{
unevaluated.clear();
unevaluated.reserve(this->containers.size());
if (this->containers.size() == 0) [[unlikely]] return;
uint_fast32_t L = this->containers[0].size();
unevaluated.emplace_back(L, std::pair<bool, T>{ false, default_value });
for (L >>= 1; L != 0; L >>= 1)
unevaluated.emplace_back(L, std::pair<bool, T>{ false, default_value });
}
constexpr LiteralLazySegmentTree(std::vector<T>&& initializer) : LiteralSegmentTree<T, Picker, default_value>(std::move(initializer))
{
unevaluated.clear();
unevaluated.reserve(this->containers.size());
if (this->containers.size() == 0) [[unlikely]] return;
uint_fast32_t L = this->containers[0].size();
unevaluated.emplace_back(L, std::pair<bool, T>{ false, default_value });
for (L >>= 1; L != 0; L >>= 1)
unevaluated.emplace_back(L, std::pair<bool, T>{ false, default_value });
}
template<typename... Args> constexpr LiteralLazySegmentTree(Args... args) : LiteralSegmentTree<T, Picker, default_value>(std::forward<Args>(args)...)
{
unevaluated.clear();
unevaluated.reserve(this->containers.size());
if (this->containers.size() == 0) [[unlikely]] return;
uint_fast32_t L = this->containers[0].size();
unevaluated.emplace_back(L, std::pair<bool, T>{ false, default_value });
for (L >>= 1; L != 0; L >>= 1)
unevaluated.emplace_back(L, std::pair<bool, T>{ false, default_value });
}
[[nodiscard]] constexpr T operator[](uint_fast32_t index) noexcept { return range_pick_up(index, index + 1); }
constexpr void update(const uint_fast32_t first_index, const uint_fast32_t end_index, const T value) noexcept
{
if (first_index >= end_index) [[unlikely]] return;
execute_evaluation_above(first_index, end_index);
uint_fast32_t cur_layer, first_index_temp = first_index, end_index_temp = end_index;
for (cur_layer = 0; first_index_temp != end_index_temp; ++cur_layer, first_index_temp >>= 1, end_index_temp >>= 1)
{
if ((first_index_temp << cur_layer) != first_index)
{
[[assume(cur_layer >= 1)]];
if (unevaluated[cur_layer - 1][(first_index >> (cur_layer - 1)) ^ 1].first)
{
this->containers[cur_layer - 1][(first_index >> (cur_layer - 1)) ^ 1] = Mapping()(this->containers[cur_layer - 1][(first_index >> (cur_layer - 1)) ^ 1], unevaluated[cur_layer - 1][(first_index >> (cur_layer - 1)) ^ 1].second, (uint_fast32_t)1 << (cur_layer - 1));
if (cur_layer != 1) [[likely]] convey_evaluation(cur_layer - 1, (first_index >> (cur_layer - 1)) ^ 1);
else unevaluated[cur_layer - 1][(first_index >> (cur_layer - 1)) ^ 1] = { false, default_value };
}
this->containers[cur_layer][first_index >> cur_layer] = Picker()(this->containers[cur_layer - 1][first_index >> (cur_layer - 1)], this->containers[cur_layer - 1][(first_index >> (cur_layer - 1)) ^ 1]);
}
if ((end_index_temp << cur_layer) != end_index)
{
[[assume(cur_layer >= 1 && end_index >= 1)]];
if (unevaluated[cur_layer - 1][((end_index - 1) >> (cur_layer - 1)) ^ 1].first)
{
this->containers[cur_layer - 1][((end_index - 1) >> (cur_layer - 1)) ^ 1] = Mapping()(this->containers[cur_layer - 1][((end_index - 1) >> (cur_layer - 1)) ^ 1], unevaluated[cur_layer - 1][((end_index - 1) >> (cur_layer - 1)) ^ 1].second, (uint_fast32_t)1 << (cur_layer - 1));
if (cur_layer != 1) [[likely]] convey_evaluation(cur_layer - 1, ((end_index - 1) >> (cur_layer - 1)) ^ 1);
else unevaluated[cur_layer - 1][((end_index - 1) >> (cur_layer - 1)) ^ 1] = { false, default_value };
}
this->containers[cur_layer][(end_index - 1) >> cur_layer] = Picker()(this->containers[cur_layer - 1][(end_index - 1) >> (cur_layer - 1)], this->containers[cur_layer - 1][((end_index - 1) >> (cur_layer - 1)) ^ 1]);
}
if (first_index_temp & 1)
{
if (unevaluated[cur_layer][first_index_temp].first)
unevaluated[cur_layer][first_index_temp].second = Composition()(unevaluated[cur_layer][first_index_temp].second, value);
else
unevaluated[cur_layer][first_index_temp] = { true, value };
this->containers[cur_layer][first_index_temp] = Mapping()(this->containers[cur_layer][first_index_temp], unevaluated[cur_layer][first_index_temp].second, (uint_fast32_t)1 << cur_layer);
if (cur_layer != 0) [[likely]] convey_evaluation(cur_layer, first_index_temp);
else unevaluated[cur_layer][first_index_temp] = { false, default_value };
++first_index_temp;
}
if (end_index_temp & 1)
{
[[assume(end_index_temp >= 1)]];
if (unevaluated[cur_layer][end_index_temp - 1].first)
unevaluated[cur_layer][end_index_temp - 1].second = Composition()(unevaluated[cur_layer][end_index_temp - 1].second, value);
else
unevaluated[cur_layer][end_index_temp - 1] = { true, value };
this->containers[cur_layer][end_index_temp - 1] = Mapping()(this->containers[cur_layer][end_index_temp - 1], unevaluated[cur_layer][end_index_temp - 1].second, (uint_fast32_t)1 << cur_layer);
if (cur_layer != 0) [[likely]] convey_evaluation(cur_layer, end_index_temp - 1);
else unevaluated[cur_layer][end_index_temp - 1] = { false, default_value };
//--end_index_temp;
}
}
for (; cur_layer != unevaluated.size(); ++cur_layer, first_index_temp >>= 1, end_index_temp >>= 1)
{
if ((first_index_temp << cur_layer) != first_index)
{
[[assume(cur_layer >= 1)]];
if (unevaluated[cur_layer - 1][(first_index >> (cur_layer - 1)) ^ 1].first)
{
this->containers[cur_layer - 1][(first_index >> (cur_layer - 1)) ^ 1] = Mapping()(this->containers[cur_layer - 1][(first_index >> (cur_layer - 1)) ^ 1], unevaluated[cur_layer - 1][(first_index >> (cur_layer - 1)) ^ 1].second, (uint_fast32_t)1 << (cur_layer - 1));
if (cur_layer != 1) [[likely]] convey_evaluation(cur_layer - 1, (first_index >> (cur_layer - 1)) ^ 1);
else unevaluated[cur_layer - 1][(first_index >> (cur_layer - 1)) ^ 1] = { false, default_value };
}
this->containers[cur_layer][first_index >> cur_layer] = Picker()(this->containers[cur_layer - 1][first_index >> (cur_layer - 1)], this->containers[cur_layer - 1][(first_index >> (cur_layer - 1)) ^ 1]);
}
if ((end_index_temp << cur_layer) != end_index)
{
[[assume(cur_layer >= 1 && end_index >= 1)]];
if (unevaluated[cur_layer - 1][((end_index - 1) >> (cur_layer - 1)) ^ 1].first)
{
this->containers[cur_layer - 1][((end_index - 1) >> (cur_layer - 1)) ^ 1] = Mapping()(this->containers[cur_layer - 1][((end_index - 1) >> (cur_layer - 1)) ^ 1], unevaluated[cur_layer - 1][((end_index - 1) >> (cur_layer - 1)) ^ 1].second, (uint_fast32_t)1 << (cur_layer - 1));
if (cur_layer != 1) [[likely]] convey_evaluation(cur_layer - 1, ((end_index - 1) >> (cur_layer - 1)) ^ 1);
else unevaluated[cur_layer - 1][((end_index - 1) >> (cur_layer - 1)) ^ 1] = { false, default_value };
}
this->containers[cur_layer][(end_index - 1) >> cur_layer] = Picker()(this->containers[cur_layer - 1][(end_index - 1) >> (cur_layer - 1)], this->containers[cur_layer - 1][((end_index - 1) >> (cur_layer - 1)) ^ 1]);
}
}
}
[[nodiscard]] constexpr T range_pick_up(const uint_fast32_t first_index, const uint_fast32_t end_index) noexcept
{
if (first_index >= end_index) return default_value;
execute_evaluation_above(first_index, end_index);
T ret_l = default_value, ret_r = default_value;
uint_fast32_t cur_layer, first_index_temp = first_index, end_index_temp = end_index;
for (cur_layer = 0; first_index_temp != end_index_temp; ++cur_layer, first_index_temp >>= 1, end_index_temp >>= 1)
{
if ((first_index_temp << cur_layer) != first_index)
{
[[assume(cur_layer >= 1)]];
if (unevaluated[cur_layer - 1][(first_index >> (cur_layer - 1)) ^ 1].first)
{
this->containers[cur_layer - 1][(first_index >> (cur_layer - 1)) ^ 1] = Mapping()(this->containers[cur_layer - 1][(first_index >> (cur_layer - 1)) ^ 1], unevaluated[cur_layer - 1][(first_index >> (cur_layer - 1)) ^ 1].second, (uint_fast32_t)1 << (cur_layer - 1));
if (cur_layer != 1) [[likely]] convey_evaluation(cur_layer - 1, (first_index >> (cur_layer - 1)) ^ 1);
else unevaluated[cur_layer - 1][(first_index >> (cur_layer - 1)) ^ 1] = { false, default_value };
}
this->containers[cur_layer][first_index >> cur_layer] = Picker()(this->containers[cur_layer - 1][first_index >> (cur_layer - 1)], this->containers[cur_layer - 1][(first_index >> (cur_layer - 1)) ^ 1]);
}
if ((end_index_temp << cur_layer) != end_index)
{
[[assume(cur_layer >= 1 && end_index >= 1)]];
if (unevaluated[cur_layer - 1][((end_index - 1) >> (cur_layer - 1)) ^ 1].first)
{
this->containers[cur_layer - 1][((end_index - 1) >> (cur_layer - 1)) ^ 1] = Mapping()(this->containers[cur_layer - 1][((end_index - 1) >> (cur_layer - 1)) ^ 1], unevaluated[cur_layer - 1][((end_index - 1) >> (cur_layer - 1)) ^ 1].second, (uint_fast32_t)1 << (cur_layer - 1));
if (cur_layer != 1) [[likely]] convey_evaluation(cur_layer - 1, ((end_index - 1) >> (cur_layer - 1)) ^ 1);
else unevaluated[cur_layer - 1][((end_index - 1) >> (cur_layer - 1)) ^ 1] = { false, default_value };
}
this->containers[cur_layer][(end_index - 1) >> cur_layer] = Picker()(this->containers[cur_layer - 1][(end_index - 1) >> (cur_layer - 1)], this->containers[cur_layer - 1][((end_index - 1) >> (cur_layer - 1)) ^ 1]);
}
if (first_index_temp & 1)
{
if (unevaluated[cur_layer][first_index_temp].first)
{
this->containers[cur_layer][first_index_temp] = Mapping()(this->containers[cur_layer][first_index_temp], unevaluated[cur_layer][first_index_temp].second, (uint_fast32_t)1 << cur_layer);
if (cur_layer != 0) [[likely]] convey_evaluation(cur_layer, first_index_temp);
else unevaluated[cur_layer][first_index_temp] = { false, default_value };
}
ret_l = Picker()(ret_l, this->containers[cur_layer][first_index_temp]);
++first_index_temp;
}
if (end_index_temp & 1)
{
[[assume(end_index_temp >= 1)]];
if (unevaluated[cur_layer][end_index_temp - 1].first)
{
this->containers[cur_layer][end_index_temp - 1] = Mapping()(this->containers[cur_layer][end_index_temp - 1], unevaluated[cur_layer][end_index_temp - 1].second, (uint_fast32_t)1 << cur_layer);
if (cur_layer != 0) [[likely]] convey_evaluation(cur_layer, end_index_temp - 1);
else unevaluated[cur_layer][end_index_temp - 1] = { false, default_value };
}
ret_r = Picker()(this->containers[cur_layer][end_index_temp - 1], ret_r);
//--end_index_temp;
}
}
for (; cur_layer != unevaluated.size(); ++cur_layer, first_index_temp >>= 1, end_index_temp >>= 1)
{
if ((first_index_temp << cur_layer) != first_index)
{
[[assume(cur_layer >= 1)]];
if (unevaluated[cur_layer - 1][(first_index >> (cur_layer - 1)) ^ 1].first)
{
this->containers[cur_layer - 1][(first_index >> (cur_layer - 1)) ^ 1] = Mapping()(this->containers[cur_layer - 1][(first_index >> (cur_layer - 1)) ^ 1], unevaluated[cur_layer - 1][(first_index >> (cur_layer - 1)) ^ 1].second, (uint_fast32_t)1 << (cur_layer - 1));
if (cur_layer != 1) [[likely]] convey_evaluation(cur_layer - 1, (first_index >> (cur_layer - 1)) ^ 1);
else unevaluated[cur_layer - 1][(first_index >> (cur_layer - 1)) ^ 1] = { false, default_value };
}
this->containers[cur_layer][first_index >> cur_layer] = Picker()(this->containers[cur_layer - 1][first_index >> (cur_layer - 1)], this->containers[cur_layer - 1][(first_index >> (cur_layer - 1)) ^ 1]);
}
if ((end_index_temp << cur_layer) != end_index)
{
[[assume(cur_layer >= 1 && end_index >= 1)]];
if (unevaluated[cur_layer - 1][((end_index - 1) >> (cur_layer - 1)) ^ 1].first)
{
this->containers[cur_layer - 1][((end_index - 1) >> (cur_layer - 1)) ^ 1] = Mapping()(this->containers[cur_layer - 1][((end_index - 1) >> (cur_layer - 1)) ^ 1], unevaluated[cur_layer - 1][((end_index - 1) >> (cur_layer - 1)) ^ 1].second, (uint_fast32_t)1 << (cur_layer - 1));
if (cur_layer != 1) [[likely]] convey_evaluation(cur_layer - 1, ((end_index - 1) >> (cur_layer - 1)) ^ 1);
else unevaluated[cur_layer - 1][((end_index - 1) >> (cur_layer - 1)) ^ 1] = { false, default_value };
}
this->containers[cur_layer][(end_index - 1) >> cur_layer] = Picker()(this->containers[cur_layer - 1][(end_index - 1) >> (cur_layer - 1)], this->containers[cur_layer - 1][((end_index - 1) >> (cur_layer - 1)) ^ 1]);
}
}
return Picker()(ret_l, ret_r);
}
};
template<typename T> using DefaultMinPicker = decltype([](const T a, const T b) { return std::min<T>(a, b); });
template<typename T, class Mapping, class Composition, class MinPicker, T default_value>
class MinLazySegmentTree : public LiteralLazySegmentTree<T, Mapping, Composition, MinPicker, default_value>
{
public:
constexpr MinLazySegmentTree(const std::vector<T>& initializer) : LiteralLazySegmentTree<T, Mapping, Composition, MinPicker, default_value>(initializer) { }
constexpr MinLazySegmentTree(std::vector<T>&& initializer) : LiteralLazySegmentTree<T, Mapping, Composition, MinPicker, default_value>(std::move(initializer)) { }
template<typename... Args> constexpr MinLazySegmentTree(Args... args) : LiteralLazySegmentTree<T, Mapping, Composition, MinPicker, default_value>(std::forward<Args>(args)...) { }
[[nodiscard]] constexpr uint_fast32_t leftest_below(const uint_fast32_t first, const uint_fast32_t last, const T limit) noexcept
{
if (this->containers.size() == 0) [[unlikely]] return 0;
if (first >= last) [[unlikely]] return this->containers[0].size();
uint_fast32_t cur_layer, cur_index;
uint_fast32_t candidate_layer = this->containers.size(), candidate_index;
uint_fast32_t first_temp = first, last_temp = last;
LiteralLazySegmentTree<T, Mapping, Composition, MinPicker, default_value>::execute_evaluation_above(first, last);
if (first & 1)
{
if (this->unevaluated[0][first].first)
{
this->containers[0][first] = Mapping()(this->containers[0][first], this->unevaluated[0][first].second, 1);
this->unevaluated[0][first] = { false, default_value };
}
if (this->containers[0][first] <= limit)
return first;
++first_temp;
}
if (last & 1)
{
if (this->unevaluated[0][last - 1].first)
{
this->containers[0][last - 1] = Mapping()(this->containers[0][last - 1], this->unevaluated[0][last - 1].second, 1);
this->unevaluated[0][last - 1] = { false, default_value };
}
if (this->containers[0][last - 1] <= limit)
candidate_layer = 0, candidate_index = last - 1;
//--last_temp;
}
for (cur_layer = 1, first_temp >>= 1, last_temp >>= 1; first_temp != last_temp; ++cur_layer, first_temp >>= 1, last_temp >>= 1)
{
if (first_temp & 1)
{
if (this->unevaluated[cur_layer][first_temp].first)
{
this->containers[cur_layer][first_temp] = Mapping()(this->containers[cur_layer][first_temp], this->unevaluated[cur_layer][first_temp].second, (uint_fast32_t)1 << cur_layer);
LiteralLazySegmentTree<T, Mapping, Composition, MinPicker, default_value>::convey_evaluation(cur_layer, first_temp);
}
if (this->containers[cur_layer][first_temp] <= limit)
break;
++first_temp;
}
if (last_temp & 1)
{
if (this->unevaluated[cur_layer][last_temp - 1].first)
{
this->containers[cur_layer][last_temp - 1] = Mapping()(this->containers[cur_layer][last_temp - 1], this->unevaluated[cur_layer][last_temp - 1].second, (uint_fast32_t)1 << cur_layer);
LiteralLazySegmentTree<T, Mapping, Composition, MinPicker, default_value>::convey_evaluation(cur_layer, last_temp - 1);
}
if (this->containers[cur_layer][last_temp - 1] <= limit)
candidate_layer = cur_layer, candidate_index = last_temp - 1;
//--last_temp;
}
}
if (first_temp != last_temp) cur_index = first_temp;
else if (candidate_layer == this->containers.size()) return this->containers[0].size();
else cur_layer = candidate_layer, cur_index = candidate_index;
while (cur_layer > 1)
{
--cur_layer, cur_index <<= 1;
if (this->unevaluated[cur_layer][cur_index].first)
{
this->containers[cur_layer][cur_index] = Mapping()(this->containers[cur_layer][cur_index], this->unevaluated[cur_layer][cur_index].second, (uint_fast32_t)1 << cur_layer);
LiteralLazySegmentTree<T, Mapping, Composition, MinPicker, default_value>::convey_evaluation(cur_layer, cur_index);
}
if (this->containers[cur_layer][cur_index] > limit)
{
cur_index |= 1;
if (this->unevaluated[cur_layer][cur_index].first)
{
this->containers[cur_layer][cur_index] = Mapping()(this->containers[cur_layer][cur_index], this->unevaluated[cur_layer][cur_index].second, (uint_fast32_t)1 << cur_layer);
LiteralLazySegmentTree<T, Mapping, Composition, MinPicker, default_value>::convey_evaluation(cur_layer, cur_index);
}
}
}
if (cur_layer == 1)
{
cur_index <<= 1;
if (this->unevaluated[0][cur_index].first)
{
this->containers[0][cur_index] = Mapping()(this->containers[0][cur_index], this->unevaluated[0][cur_index].second, 1);
this->unevaluated[0][cur_index] = { false, default_value };
}
if (this->containers[0][cur_index] > limit)
{
cur_index |= 1;
if (this->unevaluated[0][cur_index].first)
{
this->containers[0][cur_index] = Mapping()(this->containers[0][cur_index], this->unevaluated[0][cur_index].second, 1);
this->unevaluated[0][cur_index] = { false, default_value };
}
}
}
return cur_index;
}
[[nodiscard]] constexpr uint_fast32_t rightest_below(const uint_fast32_t first, const uint_fast32_t last, const T limit) noexcept
{
if (this->containers.size() == 0) [[unlikely]] return 0;
if (first >= last) [[unlikely]] return this->containers[0].size();
uint_fast32_t cur_layer, cur_index;
uint_fast32_t candidate_layer = this->containers.size(), candidate_index;
uint_fast32_t first_temp = first, last_temp = last;
LiteralLazySegmentTree<T, Mapping, Composition, MinPicker, default_value>::execute_evaluation_above(first, last);
if (last & 1)
{
if (this->unevaluated[0][last - 1].first)
{
this->containers[0][last - 1] = Mapping()(this->containers[0][last - 1], this->unevaluated[0][last - 1].second, 1);
this->unevaluated[0][last - 1] = { false, default_value };
}
if (this->containers[0][last - 1] <= limit)
return last - 1;
//--last_temp;
}
if (first & 1)
{
if (this->unevaluated[0][first].first)
{
this->containers[0][first] = Mapping()(this->containers[0][first], this->unevaluated[0][first].second, 1);
this->unevaluated[0][first] = { false, default_value };
}
if (this->containers[0][first] <= limit)
candidate_layer = 0, candidate_index = first;
++first_temp;
}
for (cur_layer = 1, first_temp >>= 1, last_temp >>= 1; first_temp != last_temp; ++cur_layer, first_temp >>= 1, last_temp >>= 1)
{
if (last_temp & 1)
{
if (this->unevaluated[cur_layer][last_temp - 1].first)
{
this->containers[cur_layer][last_temp - 1] = Mapping()(this->containers[cur_layer][last_temp - 1], this->unevaluated[cur_layer][last_temp - 1].second, (uint_fast32_t)1 << cur_layer);
LiteralLazySegmentTree<T, Mapping, Composition, MinPicker, default_value>::convey_evaluation(cur_layer, last_temp - 1);
}
if (this->containers[cur_layer][last_temp - 1] <= limit)
break;
//--last_temp;
}
if (first_temp & 1)
{
if (this->unevaluated[cur_layer][first_temp].first)
{
this->containers[cur_layer][first_temp] = Mapping()(this->containers[cur_layer][first_temp], this->unevaluated[cur_layer][first_temp].second, (uint_fast32_t)1 << cur_layer);
LiteralLazySegmentTree<T, Mapping, Composition, MinPicker, default_value>::convey_evaluation(cur_layer, first_temp);
}
if (this->containers[cur_layer][first_temp] <= limit)
candidate_layer = cur_layer, candidate_index = first_temp;
++first_temp;
}
}
if (first_temp != last_temp) cur_index = last_temp - 1;
else if (candidate_layer == this->containers.size()) return this->containers[0].size();
else cur_layer = candidate_layer, cur_index = candidate_index;
while (cur_layer > 1)
{
--cur_layer, cur_index <<= 1;
if (this->unevaluated[cur_layer][cur_index | 1].first)
{
this->containers[cur_layer][cur_index | 1] = Mapping()(this->containers[cur_layer][cur_index | 1], this->unevaluated[cur_layer][cur_index | 1].second, (uint_fast32_t)1 << cur_layer);
LiteralLazySegmentTree<T, Mapping, Composition, MinPicker, default_value>::convey_evaluation(cur_layer, cur_index | 1);
}
if (this->containers[cur_layer][cur_index | 1] <= limit)
cur_index |= 1;
else if (this->unevaluated[cur_layer][cur_index].first)
{
this->containers[cur_layer][cur_index] = Mapping()(this->containers[cur_layer][cur_index], this->unevaluated[cur_layer][cur_index].second, (uint_fast32_t)1 << cur_layer);
LiteralLazySegmentTree<T, Mapping, Composition, MinPicker, default_value>::convey_evaluation(cur_layer, cur_index);
}
}
if (cur_layer == 1)
{
cur_index <<= 1;
if (this->unevaluated[0][cur_index | 1].first)
{
this->containers[0][cur_index | 1] = Mapping()(this->containers[0][cur_index | 1], this->unevaluated[0][cur_index | 1].second, 1);
this->unevaluated[0][cur_index | 1] = { false, default_value };
}
if (this->containers[0][cur_index | 1] <= limit)
cur_index |= 1;
else if (this->unevaluated[0][cur_index].first)
{
this->containers[0][cur_index] = Mapping()(this->containers[0][cur_index], this->unevaluated[0][cur_index].second, 1);
this->unevaluated[0][cur_index] = { false, default_value };
}
}
return cur_index;
}
};
}
[[nodiscard]] static inline constexpr std::vector<std::vector<std::array<uint_least32_t, 2>>> prepare_zero(const uint_fast32_t N, [[maybe_unused]] const uint_fast32_t M, const std::vector<std::array<uint_least32_t, 4>>& edges) noexcept
{
std::vector<std::vector<std::array<uint_least32_t, 2>>> next_of(N + 1);
for (const auto& [x, l, r, c] : edges)
if (c == 0)
next_of[x].push_back({ l, r });
return next_of;
}
[[nodiscard]] static inline constexpr bool check(const uint_fast32_t N, const uint_fast32_t M, const std::vector<std::vector<std::array<uint_least32_t, 2>>>& next_of) noexcept
{
using Mapping = decltype([](const uint_least32_t target, const uint_least32_t operation, [[maybe_unused]] const uint_fast32_t length) constexpr noexcept -> uint_least32_t { return target + operation; });
using Composition = decltype([](const uint_least32_t target, const uint_least32_t operation) constexpr noexcept -> uint_least32_t { return target + operation; });
MyLib::MinLazySegmentTree<uint_least32_t, Mapping, Composition, MyLib::DefaultMinPicker<uint_least32_t>, UINT_LEAST32_MAX> in_deg(N + 1, 0);
in_deg.update(0, 1, UINT_LEAST32_MAX);
for (const auto& nexts : next_of)
for (const auto& [l, r] : nexts)
in_deg.update(l, r + 1, 1);
while (1)
{
const uint_fast32_t min_deg = in_deg.range_pick_up(1, N + 1);
if (min_deg > M) return true;
else if (min_deg > 0) return false;
const uint_fast32_t cur_pos = in_deg.leftest_below(1, N + 1, 0);
in_deg.update(cur_pos, cur_pos + 1, UINT_LEAST32_MAX);
for (const auto& [l, r] : next_of[cur_pos])
in_deg.update(l, r + 1, UINT_LEAST32_MAX);
}
}
[[nodiscard]] static inline constexpr std::vector<std::vector<std::array<uint_least32_t, 3>>> prepare(const uint_fast32_t N, [[maybe_unused]] const uint_fast32_t M, const std::vector<std::array<uint_least32_t, 4>>& edges) noexcept
{
std::vector<std::vector<std::array<uint_least32_t, 3>>> next_of(N + 1);
for (const auto& [x, l, r, c] : edges)
next_of[x].push_back({ l, r, c });
return next_of;
}
[[nodiscard]] static inline constexpr uint_fast64_t solve(const uint_fast32_t N, const std::vector<std::vector<std::array<uint_least32_t, 3>>>& next_of) noexcept
{
uint_fast64_t ans = 1;
using Mapping = decltype([](const std::pair<uint_least64_t, uint_least64_t>& target, const std::pair<uint_least64_t, uint_least64_t>& operation, [[maybe_unused]] const uint_fast32_t length) constexpr noexcept -> std::pair<uint_least64_t, uint_least64_t> { return (target.first == UINT_LEAST64_MAX || operation.first == UINT_LEAST64_MAX) ? std::make_pair(UINT_LEAST64_MAX, UINT64_C(0)) : (target.first != operation.first ? std::min(target, operation) : std::make_pair(target.first, target.second + operation.second)); });
using Composition = decltype([](const std::pair<uint_least64_t, uint_least64_t>& target, const std::pair<uint_least64_t, uint_least64_t>& operation) constexpr noexcept -> std::pair<uint_least64_t, uint_least64_t> { return (target.first == UINT_LEAST64_MAX || operation.second == UINT_LEAST64_MAX) ? std::make_pair(UINT_LEAST64_MAX, UINT64_C(0)) : (target.first != operation.first ? std::min(target, operation) : std::make_pair(target.first, target.second + operation.second)); });
constexpr std::pair<uint_least64_t, uint_least64_t> default_value = { UINT_LEAST64_MAX, UINT_LEAST64_MAX };
MyLib::MinLazySegmentTree<std::pair<uint_least64_t, uint_least64_t>, Mapping, Composition, MyLib::DefaultMinPicker<std::pair<uint_least64_t, uint_least64_t>>, default_value> dist(N + 1, std::make_pair(UINT_LEAST64_MAX - 1, UINT64_C(0)));
MyLib::LiteralSegmentTree<uint_least32_t, std::plus<uint_least32_t>, 0> count(N + 1, 1);
dist.update(1, 2, std::make_pair(UINT64_C(0), UINT64_C(1)));
std::vector<uint_least32_t> delayed_visiting;
delayed_visiting.reserve(N);
std::pair<uint_least64_t, uint_least64_t> prev_dist = { 0, 0 }, cur_dist = { 0, 0 };
while (1)
{
prev_dist = cur_dist, cur_dist = dist.range_pick_up(1, N + 1);
if (prev_dist.first != cur_dist.first)
{
for (const auto& pos : delayed_visiting)
count.update(pos, 0);
delayed_visiting.clear();
}
if (cur_dist.first >= UINT_LEAST64_MAX - 1)
break;
const uint_fast32_t cur_pos = dist.leftest_below(1, N + 1, cur_dist);
delayed_visiting.push_back(cur_pos);
for (const auto& [l, r, c] : next_of[cur_pos])
{
ans += static_cast<uint_fast64_t>(count.range_pick_up(l, r + 1)) * cur_dist.second, dist.update(l, r + 1, std::make_pair(cur_dist.first + c, cur_dist.second));
}
dist.update(cur_pos, cur_pos + 1, std::make_pair(UINT_LEAST64_MAX, UINT64_C(0)));
}
return ans;
}
int main()
{
std::cin.tie(nullptr);
std::ios::sync_with_stdio(false);
uint_fast32_t N, M;
std::cin >> N >> M;
std::vector<std::array<uint_least32_t, 4>> edges(M);
for (auto& [x, l, r, c] : edges)
std::cin >> x >> l >> r >> c;
if (!check(N, M, prepare_zero(N, M, edges)))
std::cout << "Too Many\n";
else
std::cout << solve(N, prepare(N, M, edges)) << '\n';
return 0;
}