結果
問題 |
No.3234 Infinite Propagation
|
ユーザー |
|
提出日時 | 2025-08-15 23:24:58 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 18 ms / 2,000 ms |
コード長 | 4,567 bytes |
コンパイル時間 | 3,031 ms |
コンパイル使用メモリ | 288,748 KB |
実行使用メモリ | 13,704 KB |
最終ジャッジ日時 | 2025-08-15 23:25:03 |
合計ジャッジ時間 | 4,117 ms |
ジャッジサーバーID (参考情報) |
judge6 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 18 |
ソースコード
#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) return; else if (initializer.size() == 1) { 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); 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) 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); 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)) { } constexpr T operator[](uint_fast32_t index) const noexcept { return containers[0][index]; } constexpr uint_fast32_t size() const noexcept { return containers[0].size(); } 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; } 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()) 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); } }; } static inline constexpr const char* solve(const uint_fast32_t N, const std::vector<std::string>& X, const std::vector<std::string>& Y) noexcept { uint_fast32_t length = 0; for (uint_fast32_t i = 0; i != N; ++i) length += Y[i].size(); MyLib::LiteralSegmentTree<uint_fast32_t, std::plus<uint_fast32_t>, 0> lst(length + 1, 0); for (uint_fast32_t i = 0; i != N; ++i) if (X[i] == "a") { if (Y[i].find('a') != Y[i].npos) return "Yes"; else lst.update(Y[i].size(), 1); } for (uint_fast32_t i = 0; i != N; ++i) if (X[i].find('a') == X[i].npos && lst.range_pick_up(X[i].size(), length + 1) > 0) return "Yes"; return "No"; } int main() { std::cin.tie(nullptr); std::ios::sync_with_stdio(false); uint_fast32_t T, i; std::cin >> T; for (i = 0; i != T; ++i) { uint_fast32_t N, i; std::cin >> N; std::vector<std::string> X(N), Y(N); for (i = 0; i != N; ++i) std::cin >> X[i] >> Y[i]; std::cout << solve(N, X, Y) << '\n'; } return 0; }