comp-library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub luzhiled1333/comp-library

:heavy_check_mark: test/atcoder/abc258_e/online-algorithm.test.cpp

Depends on

Code

// 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/online-query/online-query-jump-on-functional-graph.hpp"

#include <iostream>
#include <numeric>
#include <vector>

namespace luz {

  void main_() {
    using edge  = Edge< i32 >;
    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();
    OnlineJumpOnFunctionalGraphQuery online_jump_solver(fg);
    for ([[maybe_unused]] usize _: rep(0, q)) {
      u64 k;
      std::cin >> k;
      usize v = online_jump_solver.jump(0, k - 1);
      std::cout << ans[v] << std::endl;
    }
  }

} // namespace luz

int main() {
  luz::main_();
}
#line 1 "test/atcoder/abc258_e/online-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/online-query/online-query-jump-on-functional-graph.hpp"

#line 2 "src/utility/bit/bit-width.hpp"

#line 2 "src/utility/bit/popcount.hpp"

#line 5 "src/utility/bit/popcount.hpp"

#line 7 "src/utility/bit/popcount.hpp"

namespace luz {

  usize popcount(u64 x) {
    assert(__cplusplus <= 201703L);

#ifdef __GNUC__
    return __builtin_popcountll(x);
#endif

    x -= (x >> 1) & 0x5555555555555555;
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333);
    x += (x >> 4) & 0x0f0f0f0f0f0f0f0f;
    return x * 0x0101010101010101 >> 56 & 0x7f;
  }

} // namespace luz
#line 6 "src/utility/bit/bit-width.hpp"

#line 8 "src/utility/bit/bit-width.hpp"

namespace luz {

  usize bit_width(u64 x) {
    assert(__cplusplus <= 201703L);

    if (x == 0) {
      return 0;
    }

#ifdef __GNUC__
    return 64 - __builtin_clzll(x);
#endif

    x |= x >> 1;
    x |= x >> 2;
    x |= x >> 4;
    x |= x >> 8;
    x |= x >> 16;
    x |= x >> 32;
    return popcount(x);
  }

} // namespace luz
#line 7 "src/graph/functional-graph/online-query/online-query-jump-on-functional-graph.hpp"

#line 9 "src/graph/functional-graph/online-query/online-query-jump-on-functional-graph.hpp"
#include <utility>
#line 11 "src/graph/functional-graph/online-query/online-query-jump-on-functional-graph.hpp"

namespace luz {

  template < class G >
  class OnlineJumpOnFunctionalGraphQuery {
    using graph     = G;
    using cost_type = typename graph::cost_type;

    usize g_size;
    graph g;

    usize LOG;
    std::vector< std::vector< usize > > doubling_table;

    std::vector< usize > loop_id, loop_size, loop_pos;
    std::vector< std::vector< usize > > loops;

    void check_functional_graph() const {
      for (usize v: rep(0, g_size)) {
        assert(g[v].size() == 1);
      }
    }

    void build_doubling_table() {
      for (usize k: rep(0, LOG)) {
        for (usize v: rep(0, g_size)) {
          doubling_table[k][v] =
              (k ? doubling_table[k - 1][doubling_table[k - 1][v]]
                 : g[v][0].to);
        }
      }
    }

    std::vector< usize > get_indegrees() const {
      std::vector< usize > indegrees(g_size);
      for (usize v: rep(0, g_size)) {
        indegrees[g[v][0].to]++;
      }
      return indegrees;
    }

    void delete_leaves(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 v = leaves.back();
        leaves.pop_back();

        usize u = g[v][0].to;
        indegrees[u]--;

        if (indegrees[u] == 0) {
          leaves.emplace_back(u);
        }
      }
    }

    void construct_loops() {
      std::vector< usize > indegrees = get_indegrees();
      delete_leaves(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));
      }
    }

    usize jump_small(usize v, usize k) const {
      assert(k < g_size);

      for (usize i: rep(0, LOG)) {
        if ((k & 1) == 1) {
          v = doubling_table[i][v];
        }
        k >>= 1;
      }
      return v;
    }

   public:
    OnlineJumpOnFunctionalGraphQuery(const graph &g_)
        : g_size(g_.size()),
          g(g_),
          LOG(bit_width(g_size - 1)),
          doubling_table(LOG, std::vector< usize >(g_size)),
          loop_id(g_size, -1),
          loop_size(g_size),
          loop_pos(g_size, -1) {
      check_functional_graph();
      assert(g_size != 0);

      build_doubling_table();
      construct_loops();
    }

    usize jump(usize v, u64 k) const {
      assert(v < g_size);

      if (k == 0) {
        return v;
      }

      if (k < g_size) {
        return jump_small(v, k);
      }

      v = jump_small(v, g_size - 1);
      k -= (g_size - 1);

      const auto &loop = loops[loop_id[v]];
      k += loop_pos[v];
      k %= loop_size[v];
      return loop[k];
    }
  };

} // namespace luz
#line 10 "test/atcoder/abc258_e/online-algorithm.test.cpp"

#line 12 "test/atcoder/abc258_e/online-algorithm.test.cpp"
#include <numeric>
#line 14 "test/atcoder/abc258_e/online-algorithm.test.cpp"

namespace luz {

  void main_() {
    using edge  = Edge< i32 >;
    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();
    OnlineJumpOnFunctionalGraphQuery online_jump_solver(fg);
    for ([[maybe_unused]] usize _: rep(0, q)) {
      u64 k;
      std::cin >> k;
      usize v = online_jump_solver.jump(0, k - 1);
      std::cout << ans[v] << std::endl;
    }
  }

} // namespace luz

int main() {
  luz::main_();
}
Back to top page