This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub luzhiled1333/comp-library
// verification-helper: PROBLEM https://atcoder.jp/contests/abc258/tasks/abc258_e #include "src/cpp-template/header/int-alias.hpp" #include "src/cpp-template/header/rep.hpp" #include "src/cpp-template/header/size-alias.hpp" #include "src/cpp-template/header/vector-ios.hpp" #include "src/graph/class/edge/edge.hpp" #include "src/graph/class/static-graph.hpp" #include "src/graph/functional-graph/offline-query/offline-query-jump-on-functional-graph.hpp" #include <iostream> #include <numeric> #include <vector> namespace luz { void main_() { using edge = Edge< i64 >; using graph = StaticGraph< edge >; usize n, q, x; std::cin >> n >> q >> x; std::vector< i64 > ws(n); std::cin >> ws; i64 sum_w = std::accumulate(ws.begin(), ws.end(), i64()); i64 xp = x % sum_w; std::vector< i64 > ans(n, x / sum_w * n); ws.resize(2 * n + 1); for (usize i: rep(0, n)) { ws[n + i] = ws[i]; } for (usize i: rrep(0, 2 * n)) { ws[i] += ws[i + 1]; } graph fg(n); usize r = 0; for (usize l: rep(0, n)) { while (ws[l] - ws[r] < xp) { r++; } fg.add_directed_edge(l, r % n); ans[l] += r - l; } fg.initialize(); std::vector< u64 > qs(q); OfflineJumpOnFunctionalGraphQuery offline_jump_on_functional_graph_solver(fg); for (usize i: rep(0, q)) { std::cin >> qs[i]; --qs[i]; offline_jump_on_functional_graph_solver.add_query(0, qs[i]); } offline_jump_on_functional_graph_solver.build(); for (usize i: rep(0, q)) { std::cout << ans[offline_jump_on_functional_graph_solver.jump( 0, qs[i])] << std::endl; } } } // namespace luz int main() { luz::main_(); }
#line 1 "test/atcoder/abc258_e/offline-algorithm.test.cpp" // verification-helper: PROBLEM https://atcoder.jp/contests/abc258/tasks/abc258_e #line 2 "src/cpp-template/header/int-alias.hpp" #include <cstdint> namespace luz { using i32 = std::int32_t; using i64 = std::int64_t; using i128 = __int128_t; using u32 = std::uint32_t; using u64 = std::uint64_t; using u128 = __uint128_t; } // namespace luz #line 2 "src/cpp-template/header/rep.hpp" #line 2 "src/cpp-template/header/size-alias.hpp" #include <cstddef> namespace luz { using isize = std::ptrdiff_t; using usize = std::size_t; } // namespace luz #line 4 "src/cpp-template/header/rep.hpp" #include <algorithm> namespace luz { struct rep { struct itr { usize i; constexpr itr(const usize i) noexcept: i(i) {} void operator++() noexcept { ++i; } constexpr usize operator*() const noexcept { return i; } constexpr bool operator!=(const itr x) const noexcept { return i != x.i; } }; const itr f, l; constexpr rep(const usize f, const usize l) noexcept : f(std::min(f, l)), l(l) {} constexpr auto begin() const noexcept { return f; } constexpr auto end() const noexcept { return l; } }; struct rrep { struct itr { usize i; constexpr itr(const usize i) noexcept: i(i) {} void operator++() noexcept { --i; } constexpr usize operator*() const noexcept { return i; } constexpr bool operator!=(const itr x) const noexcept { return i != x.i; } }; const itr f, l; constexpr rrep(const usize f, const usize l) noexcept : f(l - 1), l(std::min(f, l) - 1) {} constexpr auto begin() const noexcept { return f; } constexpr auto end() const noexcept { return l; } }; } // namespace luz #line 2 "src/cpp-template/header/vector-ios.hpp" #line 4 "src/cpp-template/header/vector-ios.hpp" #include <iostream> #include <vector> namespace luz { template < typename T > std::ostream &operator<<(std::ostream &os, const std::vector< T > vs) { for (usize i: rep(0, vs.size())) { os << vs[i] << (i + 1 != vs.size() ? " " : ""); } return os; } template < typename T > std::istream &operator>>(std::istream &is, std::vector< T > &vs) { for (T &v: vs) { is >> v; } return is; } } // namespace luz #line 2 "src/graph/class/edge/edge.hpp" #line 4 "src/graph/class/edge/edge.hpp" #line 6 "src/graph/class/edge/edge.hpp" namespace luz { template < typename T > class Edge { public: using cost_type = T; usize from, to; T cost; usize id; Edge() = default; Edge(usize from_, usize to_, T cost_, usize id_) : from(from_), to(to_), cost(cost_), id(id_) {} }; template < typename T > using Edges = std::vector< Edge< T > >; } // namespace luz #line 2 "src/graph/class/static-graph.hpp" #line 5 "src/graph/class/static-graph.hpp" #line 7 "src/graph/class/static-graph.hpp" #include <cassert> #line 9 "src/graph/class/static-graph.hpp" namespace luz::internal { template < typename Iterator > class OutgoingEdges { Iterator f, l; public: OutgoingEdges(Iterator f, Iterator l): f(f), l(l) {} Iterator begin() const { return f; } Iterator end() const { return l; } usize size() const { return l - f; } auto &operator[](usize k) { assert(k < size()); return begin()[k]; } const auto &operator[](usize k) const { assert(k < size()); return begin()[k]; } }; } // namespace luz::internal namespace luz { template < typename Edge > class StaticGraph { using Edges = std::vector< Edge >; using iterator = typename Edges::iterator; using const_iterator = typename Edges::const_iterator; template < typename Iterator > using Es = internal::OutgoingEdges< Iterator >; protected: bool initialized; usize vertex_count; usize edge_count; Edges edges; std::vector< usize > outdegrees; public: using cost_type = typename Edge::cost_type; StaticGraph() = default; explicit StaticGraph(usize n) : initialized(false), vertex_count(n), edge_count(0), outdegrees(vertex_count) {} usize size() const { return vertex_count; } void initialize() { assert(not initialized); outdegrees.emplace_back(0); for (usize i: rrep(0, size())) { outdegrees[i] += outdegrees[i + 1]; } std::sort(edges.begin(), edges.end(), [](const Edge &e1, const Edge &e2) { return e1.from != e2.from ? e1.from > e2.from : e1.to < e2.to; }); initialized = true; } void add_directed_edge(usize from, usize to, cost_type cost = 1) { assert(not initialized); assert(from < size()); assert(to < size()); edges.emplace_back(from, to, cost, edge_count++); outdegrees[from]++; } void add_undirected_edge(usize u, usize v, cost_type cost = 1) { assert(not initialized); assert(u < size()); assert(v < size()); assert(u != v); edges.emplace_back(u, v, cost, edge_count); outdegrees[u]++; edges.emplace_back(v, u, cost, edge_count++); outdegrees[v]++; } Es< iterator > operator[](const usize &v) { assert(initialized); return Es< iterator >(edges.begin() + outdegrees[v + 1], edges.begin() + outdegrees[v]); } const Es< const_iterator > operator[](const usize &v) const { assert(initialized); return Es< const_iterator >(edges.cbegin() + outdegrees[v + 1], edges.cbegin() + outdegrees[v]); } }; } // namespace luz #line 2 "src/graph/functional-graph/offline-query/offline-query-jump-on-functional-graph.hpp" #line 2 "src/graph/tree/offline-query/offline-query-level-ancestor.hpp" #line 2 "src/utility/pair-hash.hpp" #line 4 "src/utility/pair-hash.hpp" #include <functional> #include <utility> namespace luz { class PairHash { template < typename T > usize hash_combine(usize hr, const T &x) const { usize h = std::hash< T >()(x); return hr ^ (h + (hr << 11) + (hr >> 13)); } public: template < typename F, typename S > usize operator()(const std::pair< F, S > &p) const { return hash_combine(hash_combine(0, p.first), p.second); } }; } // namespace luz #line 6 "src/graph/tree/offline-query/offline-query-level-ancestor.hpp" #line 8 "src/graph/tree/offline-query/offline-query-level-ancestor.hpp" #include <optional> #include <unordered_map> #line 12 "src/graph/tree/offline-query/offline-query-level-ancestor.hpp" namespace luz { template < class G > class OfflineLAQuery { using graph = G; using cost_type = typename graph::cost_type; usize g_size; graph g; usize query_count; std::vector< std::vector< usize > > qs; std::vector< bool > visited; std::vector< usize > path; using query_type = std::pair< usize, usize >; std::unordered_map< query_type, std::optional< usize >, PairHash > results; void bound_check(usize v) const { assert(v < g_size); } void dfs(usize v) { visited[v] = true; path.emplace_back(v); for (const auto &level: qs[v]) { if (level < path.size()) { results[query_type(v, level)] = path[level]; } } for (const auto &e: g[v]) { if (visited[e.to]) continue; dfs(e.to); } path.pop_back(); } public: explicit OfflineLAQuery() = default; explicit OfflineLAQuery(graph &g) : g_size(g.size()), g(g), query_count(0), qs(g_size), visited(g_size, false) {} void add_query(usize v, usize level) { bound_check(v); qs[v].emplace_back(level); query_count++; } void build(usize root) { bound_check(root); results.reserve(query_count); path.reserve(g_size); dfs(root); } std::optional< usize > la(usize v, usize level) const { bound_check(v); query_type qi(v, level); assert(results.count(qi)); return (*results.find(qi)).second; } }; } // namespace luz #line 8 "src/graph/functional-graph/offline-query/offline-query-jump-on-functional-graph.hpp" #line 13 "src/graph/functional-graph/offline-query/offline-query-jump-on-functional-graph.hpp" namespace luz { template < class G > class OfflineJumpOnFunctionalGraphQuery { using graph = G; using cost_type = typename graph::cost_type; usize g_size; graph g; graph tree; usize tree_root; std::vector< usize > tree_depth, subtree_roots; std::vector< usize > loop_id, loop_size, loop_pos; std::vector< std::vector< usize > > loops; using query_type = std::pair< usize, u64 >; std::vector< query_type > qs; std::unordered_map< query_type, usize, PairHash > result; void dfs_on_subtree(usize v, usize p) { for (auto &e: tree[v]) { usize u = e.to; if (u == p) continue; subtree_roots[u] = subtree_roots[v]; tree_depth[u] = tree_depth[v] + 1; dfs_on_subtree(u, v); } } std::vector< usize > get_indegrees() const { std::vector< usize > indegrees(g_size); for (usize v: rep(0, g_size)) { for (auto e: g[v]) { indegrees[e.to]++; } } return indegrees; } void construct_tree(std::vector< usize > &indegrees) { std::vector< usize > leaves; leaves.reserve(g_size); for (usize v: rep(0, g_size)) { if (indegrees[v] > 0) { continue; } leaves.emplace_back(v); } while (not leaves.empty()) { usize child = leaves.back(); leaves.pop_back(); usize parent = g[child][0].to; indegrees[parent]--; tree.add_undirected_edge(parent, child); if (indegrees[parent] == 0) { leaves.emplace_back(parent); } } for (usize v: rep(0, g_size)) { if (indegrees[v] == 0) { continue; } tree.add_undirected_edge(tree_root, v); } tree.initialize(); for (usize v: rep(0, g_size)) { if (indegrees[v] == 0) { continue; } subtree_roots[v] = v; dfs_on_subtree(v, tree_root); } } void construct_loops(std::vector< usize > &indegrees) { for (usize v: rep(0, g_size)) { if (indegrees[v] == 0) { continue; } usize cur = v; std::vector< usize > loop; do { loop_id[cur] = loops.size(); loop_pos[cur] = loop.size(); loop.emplace_back(cur); indegrees[cur] = 0; cur = g[cur][0].to; } while (cur != v); do { loop_size[cur] = loop.size(); cur = g[cur][0].to; } while (cur != v); loops.emplace_back(std::move(loop)); } } public: explicit OfflineJumpOnFunctionalGraphQuery(const graph &g_) : g_size(g_.size()), g(g_), tree(g_size + 1), tree_root(g_size), tree_depth(g_size), subtree_roots(g_size), loop_id(g_size), loop_size(g_size), loop_pos(g_size) { for (usize v: rep(0, g_size)) { assert(g[v].size() == 1); } std::vector< usize > indegrees = get_indegrees(); construct_tree(indegrees); construct_loops(indegrees); } void add_query(usize v, u64 k) { qs.emplace_back(v, k); } void build() { OfflineLAQuery la_solver(tree); result.reserve(qs.size()); for (auto [v, k]: qs) { if (k < tree_depth[v]) { la_solver.add_query(v, tree_depth[v] - k + 1); } else { query_type qi(v, k); k -= tree_depth[v]; usize root = subtree_roots[v]; const auto &loop = loops[loop_id[root]]; k += loop_pos[root]; k %= loop_size[root]; result[qi] = loop[k]; } } la_solver.build(g_size); for (auto [v, k]: qs) { if (tree_depth[v] <= k) { continue; } query_type qi(v, k); result[qi] = la_solver.la(v, tree_depth[v] - k + 1).value(); } } usize jump(usize v, u64 k) const { query_type qi(v, k); assert(result.count(qi)); return result.find(qi)->second; } }; } // namespace luz #line 10 "test/atcoder/abc258_e/offline-algorithm.test.cpp" #line 12 "test/atcoder/abc258_e/offline-algorithm.test.cpp" #include <numeric> #line 14 "test/atcoder/abc258_e/offline-algorithm.test.cpp" namespace luz { void main_() { using edge = Edge< i64 >; using graph = StaticGraph< edge >; usize n, q, x; std::cin >> n >> q >> x; std::vector< i64 > ws(n); std::cin >> ws; i64 sum_w = std::accumulate(ws.begin(), ws.end(), i64()); i64 xp = x % sum_w; std::vector< i64 > ans(n, x / sum_w * n); ws.resize(2 * n + 1); for (usize i: rep(0, n)) { ws[n + i] = ws[i]; } for (usize i: rrep(0, 2 * n)) { ws[i] += ws[i + 1]; } graph fg(n); usize r = 0; for (usize l: rep(0, n)) { while (ws[l] - ws[r] < xp) { r++; } fg.add_directed_edge(l, r % n); ans[l] += r - l; } fg.initialize(); std::vector< u64 > qs(q); OfflineJumpOnFunctionalGraphQuery offline_jump_on_functional_graph_solver(fg); for (usize i: rep(0, q)) { std::cin >> qs[i]; --qs[i]; offline_jump_on_functional_graph_solver.add_query(0, qs[i]); } offline_jump_on_functional_graph_solver.build(); for (usize i: rep(0, q)) { std::cout << ans[offline_jump_on_functional_graph_solver.jump( 0, qs[i])] << std::endl; } } } // namespace luz int main() { luz::main_(); }