src/data_structure/segment_tree/waitings.hpp

• View this file on GitHub
• Last update: 2020-12-25 02:08:14+09:00
• Include: #include "src/data_structure/segment_tree/waitings.hpp"

Required by

• Lazy Segment Tree (src/data_structure/segment_tree/lazy.hpp)

Verified with

• test/aizu-online-judge/2450.test.cpp
• test/library-checker/range_affine_range_sum.test.cpp

Code

#pragma once

#include <cstdint>
#include <queue>

namespace workspace {

namespace internal {

struct waitings : std::queue<size_t> {
  waitings(size_t n) : in(n) {}

  bool push(size_t index) {
    // assert(index < in.size());
    if (in[index]) return false;
    emplace(index);
    return (in[index] = true);
  }

  size_t pop() {
    // assert(!empty());
    auto index = front();
    std::queue<size_t>::pop();
    in[index] = false;
    return index;
  }

 private:
  std::vector<int_least8_t> in;
};

}  // namespace internal

}  // namespace workspace

#line 2 "src/data_structure/segment_tree/waitings.hpp"

#include <cstdint>
#include <queue>

namespace workspace {

namespace internal {

struct waitings : std::queue<size_t> {
  waitings(size_t n) : in(n) {}

  bool push(size_t index) {
    // assert(index < in.size());
    if (in[index]) return false;
    emplace(index);
    return (in[index] = true);
  }

  size_t pop() {
    // assert(!empty());
    auto index = front();
    std::queue<size_t>::pop();
    in[index] = false;
    return index;
  }

 private:
  std::vector<int_least8_t> in;
};

}  // namespace internal

}  // namespace workspace

Back to top page