結果
| 問題 |
No.3327 うるせぇ、ポリオミノぶつけんぞ
|
| コンテスト | |
| ユーザー |
 elphe
|
| 提出日時 | 2025-10-25 16:28:35 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 76 ms / 3,000 ms |
| コード長 | 8,289 bytes |
| コンパイル時間 | 3,072 ms |
| コンパイル使用メモリ | 291,552 KB |
| 実行使用メモリ | 7,720 KB |
| 最終ジャッジ日時 | 2025-10-25 16:28:45 |
| 合計ジャッジ時間 | 8,973 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 24 |
コンパイルメッセージ
In member function ‘constexpr uint_fast32_t MyLib::MaxSegmentTree<T, MaxPicker, default_value>::leftest_above(uint_fast32_t, uint_fast32_t, T) const [with T = unsigned int; MaxPicker = MyLib::<lambda(unsigned int, unsigned int)>; T default_value = 0]’,
inlined from ‘constexpr std::vector<int> solve(uint_fast32_t, uint_fast32_t, std::vector<unsigned int>&&, const std::vector<std::pair<char, unsigned int> >&)’ at main.cpp:214:49,
inlined from ‘int main()’ at main.cpp:247:14:
main.cpp:154:56: warning: ‘candidate_index’ may be used uninitialized [-Wmaybe-uninitialized]
154 | --cur_layer, cur_index <<= 1;
| ~~~~~~~~~~^~~~~
main.cpp: In function ‘int main()’:
main.cpp:129:82: note: ‘candidate_index’ was declared here
129 | uint_fast32_t candidate_layer = this->containers.size(), candidate_index;
| ^~~~~~~~~~~~~~~
ソースコード
#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> using DefaultMaxPicker = decltype([](const T a, const T b) { return std::max<T>(a, b); });
template<typename T, class MaxPicker, T default_value = std::numeric_limits<T>::lowest()>
class MaxSegmentTree : public LiteralSegmentTree<T, MaxPicker, default_value>
{
public:
constexpr MaxSegmentTree(const std::vector<T>& initializer) : LiteralSegmentTree<T, MaxPicker, default_value>(initializer) { }
constexpr MaxSegmentTree(std::vector<T>&& initializer) : LiteralSegmentTree<T, MaxPicker, default_value>(std::move(initializer)) { }
template<typename... Args> constexpr MaxSegmentTree(const Args... args) : LiteralSegmentTree<T, MaxPicker, default_value>(std::forward<Args>(args)...) { }
[[nodiscard]] constexpr uint_fast32_t leftest_above(const uint_fast32_t first, const uint_fast32_t last, const T limit) const noexcept
{
[[assume(first <= last)]];
if (this->containers.size() == 0) [[unlikely]] return 0;
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;
for (cur_layer = 0; first_temp != last_temp; ++cur_layer, first_temp >>= 1, last_temp >>= 1)
{
if (first_temp & 1)
{
if (this->containers[cur_layer][first_temp] >= limit)
break;
++first_temp;
}
if (last_temp & 1)
{
[[assume(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 != 0)
{
--cur_layer, cur_index <<= 1;
if (this->containers[cur_layer][cur_index] < limit)
cur_index |= 1;
}
return cur_index;
}
[[nodiscard]] constexpr uint_fast32_t rightest_above(const uint_fast32_t first, const uint_fast32_t last, const T limit) const noexcept
{
[[assume(first <= last)]];
if (this->containers.size() == 0) [[unlikely]] return 0;
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;
for (cur_layer = 0; first_temp != last_temp; ++cur_layer, first_temp >>= 1, last_temp >>= 1)
{
if (last_temp & 1)
{
[[assume(last_temp >= 1)]];
if (this->containers[cur_layer][last_temp - 1] >= limit)
break;
//--last_temp;
}
if (first_temp & 1)
{
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 != 0)
{
--cur_layer, cur_index <<= 1;
if (this->containers[cur_layer][cur_index | 1] >= limit)
cur_index |= 1;
}
return cur_index;
}
};
}
[[nodiscard]] static inline constexpr std::vector<int_least32_t> solve(const uint_fast32_t N, const uint_fast32_t Q, std::vector<uint_least32_t>&& A, const std::vector<std::pair<char, uint_least32_t>>& queries) noexcept
{
MyLib::MaxSegmentTree<uint_least32_t, MyLib::DefaultMaxPicker<uint_least32_t>> cyans(std::move(A));
std::vector<int_least32_t> ans;
ans.reserve(Q);
for (const auto& [c, x] : queries)
{
if (c == '1')
{
const uint_fast32_t pos = cyans.leftest_above(0, N, x + 1);
if (pos >= N) ans.push_back(-1);
else ans.push_back(pos + 1), cyans.update(pos, 0);
}
else
{
const uint_fast32_t pos = cyans.rightest_above(0, N, x + 1);
if (pos >= N) ans.push_back(-1);
else ans.push_back(pos + 1), cyans.update(pos, 0);
}
}
return ans;
}
static inline void output(const std::vector<int_least32_t>& ans) noexcept
{
for (const auto& res : ans)
std::cout << res << '\n';
}
int main()
{
std::cin.tie(nullptr);
std::ios::sync_with_stdio(false);
uint_fast32_t N, Q;
std::cin >> N >> Q;
std::vector<uint_least32_t> A(N);
std::vector<std::pair<char, uint_least32_t>> queries(Q);
for (auto& a : A) std::cin >> a;
for (auto& [c, x] : queries) std::cin >> c >> x;
output(solve(N, Q, std::move(A), queries));
return 0;
}