proconlib

This documentation is automatically generated by competitive-verifier/competitive-verifier

View the Project on GitHub anqooqie/proconlib

:heavy_check_mark: tests/second_order_imos.test.cpp

Depends on

Code

// competitive-verifier: STANDALONE

#include <algorithm>
#include <iostream>
#include <random>
#include <ranges>
#include <tuple>
#include <vector>
#include "tools/assert_that.hpp"
#include "tools/second_order_imos.hpp"

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);

  std::random_device seed_gen;
  std::mt19937 engine(seed_gen());
  tools::second_order_imos<int> a(10);
  std::vector<int> b(a.size(), 0);
  std::uniform_int_distribution<int> x_dist(-10, 10);
  std::uniform_int_distribution<int> d_dist(-3, 3);
  for (int L = 0; L < a.size(); ++L) {
    std::uniform_int_distribution<int> lr_dist(L, a.size());
    for (int q = 0; q < 100; ++q) {
      auto l = lr_dist(engine);
      auto r = lr_dist(engine);
      std::tie(l, r) = std::minmax({l, r});
      const auto x = x_dist(engine);
      const auto d = d_dist(engine);
      a.add(l, r, x, d);
      for (int i = l; i < r; ++i) {
        b[i] += x + (i - l) * d;
      }
    }
    for (int i = 0; i <= L; ++i) {
      assert_that(a[i] == b[i]);
    }
  }
  assert_that((a | std::ranges::to<std::vector>()) == b);

  return 0;
}

#line 1 "tests/second_order_imos.test.cpp"
// competitive-verifier: STANDALONE

#include <algorithm>
#include <iostream>
#include <random>
#include <ranges>
#include <tuple>
#include <vector>
#line 1 "tools/assert_that.hpp"



#line 5 "tools/assert_that.hpp"
#include <cstdlib>

#define assert_that_impl(cond, file, line, func) do {\
  if (!cond) {\
    std::cerr << file << ':' << line << ": " << func << ": Assertion `" << #cond << "' failed." << '\n';\
    std::exit(EXIT_FAILURE);\
  }\
} while (false)
#define assert_that(...) assert_that_impl((__VA_ARGS__), __FILE__, __LINE__, __func__)


#line 1 "tools/second_order_imos.hpp"



#include <cassert>
#include <compare>
#include <cstddef>
#include <iterator>
#line 1 "tools/non_bool_integral.hpp"



#include <concepts>
#include <type_traits>
#line 1 "tools/integral.hpp"



#line 1 "tools/is_integral.hpp"



#line 5 "tools/is_integral.hpp"

namespace tools {
  template <typename T>
  struct is_integral : std::is_integral<T> {};

  template <typename T>
  inline constexpr bool is_integral_v = tools::is_integral<T>::value;
}


#line 5 "tools/integral.hpp"

namespace tools {
  template <typename T>
  concept integral = tools::is_integral_v<T>;
}


#line 7 "tools/non_bool_integral.hpp"

namespace tools {
  template <typename T>
  concept non_bool_integral = tools::integral<T> && !std::same_as<std::remove_cv_t<T>, bool>;
}


#line 10 "tools/second_order_imos.hpp"

namespace tools {
  template <tools::non_bool_integral T>
  class second_order_imos {
    std::vector<T> m_vector;
    std::vector<T> m_diffs2;
    int m_processed;

  public:
    class iterator {
      second_order_imos<T> *m_parent;
      std::size_t m_i;

    public:
      using reference = const T&;
      using value_type = T;
      using difference_type = std::ptrdiff_t;
      using pointer = const T*;
      using iterator_category = std::random_access_iterator_tag;

      iterator() = default;
      iterator(second_order_imos<T> * const parent, const std::size_t i) : m_parent(parent), m_i(i) {
      }

      reference operator*() const {
        return (*this->m_parent)[this->m_i];
      }
      pointer operator->() const {
        return &(*(*this));
      }

      iterator& operator++() {
        ++this->m_i;
        return *this;
      }
      iterator operator++(int) {
        const auto self = *this;
        ++*this;
        return self;
      }
      iterator& operator--() {
        --this->m_i;
        return *this;
      }
      iterator operator--(int) {
        const auto self = *this;
        --*this;
        return self;
      }
      iterator& operator+=(const difference_type n) {
        this->m_i += n;
        return *this;
      }
      iterator& operator-=(const difference_type n) {
        this->m_i -= n;
        return *this;
      }
      friend iterator operator+(const iterator self, const difference_type n) {
        return iterator(self.m_parent, self.m_i + n);
      }
      friend iterator operator+(const difference_type n, const iterator self) {
        return self + n;
      }
      friend iterator operator-(const iterator self, const difference_type n) {
        return iterator(self.m_parent, self.m_i - n);
      }
      friend difference_type operator-(const iterator lhs, const iterator rhs) {
        assert(lhs.m_parent == rhs.m_parent);
        return static_cast<difference_type>(lhs.m_i) - static_cast<difference_type>(rhs.m_i);
      }
      reference operator[](const difference_type n) const {
        return *(*this + n);
      }

      friend std::strong_ordering operator<=>(const iterator lhs, const iterator rhs) {
        assert(lhs.m_parent == rhs.m_parent);
        return lhs.m_i <=> rhs.m_i;
      }
      friend bool operator==(const iterator lhs, const iterator rhs) {
        assert(lhs.m_parent == rhs.m_parent);
        return lhs.m_i == rhs.m_i;
      }
    };

    second_order_imos() : second_order_imos(0) {
    }
    second_order_imos(const int n) : m_vector(n, 0), m_diffs2(n + 2, 0), m_processed(0) {
    }

    int size() const {
      return this->m_vector.size();
    }
    const T& operator[](const int i) {
      assert(0 <= i && i < this->size());
      auto& j = this->m_processed;
      do {
        if (i < j) break;
        if (j == 0) {
          this->m_vector[j] = this->m_diffs2[j];
          ++j;
          if (i < j) break;
        }
        if (j == 1) {
          this->m_vector[j] = this->m_diffs2[j] + 2 * this->m_vector[j - 1];
          ++j;
          if (i < j) break;
        }
        do {
          this->m_vector[j] = this->m_diffs2[j] + 2 * this->m_vector[j - 1] - this->m_vector[j - 2];
          ++j;
        } while (j <= i);
      } while (false);
      return this->m_vector[i];
    }

    iterator begin() { return iterator(this, 0); }
    iterator end() { return iterator(this, this->size()); }
    std::reverse_iterator<iterator> rbegin() { return std::make_reverse_iterator(this->end()); }
    std::reverse_iterator<iterator> rend() { return std::make_reverse_iterator(this->begin()); }

    void add(const int l, const int r, const T a, const T d) {
      assert(0 <= l && l <= r && r <= this->size());
      assert(this->m_processed <= l);
      this->m_diffs2[l] += a;
      this->m_diffs2[l + 1] += d - a;
      this->m_diffs2[r] -= a + (r - l) * d;
      this->m_diffs2[r + 1] += a + (r - l - 1) * d;
    }
  };
}


#line 11 "tests/second_order_imos.test.cpp"

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);

  std::random_device seed_gen;
  std::mt19937 engine(seed_gen());
  tools::second_order_imos<int> a(10);
  std::vector<int> b(a.size(), 0);
  std::uniform_int_distribution<int> x_dist(-10, 10);
  std::uniform_int_distribution<int> d_dist(-3, 3);
  for (int L = 0; L < a.size(); ++L) {
    std::uniform_int_distribution<int> lr_dist(L, a.size());
    for (int q = 0; q < 100; ++q) {
      auto l = lr_dist(engine);
      auto r = lr_dist(engine);
      std::tie(l, r) = std::minmax({l, r});
      const auto x = x_dist(engine);
      const auto d = d_dist(engine);
      a.add(l, r, x, d);
      for (int i = l; i < r; ++i) {
        b[i] += x + (i - l) * d;
      }
    }
    for (int i = 0; i <= L; ++i) {
      assert_that(a[i] == b[i]);
    }
  }
  assert_that((a | std::ranges::to<std::vector>()) == b);

  return 0;
}
Back to top page