matsutaku-library

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

View the Project on GitHub MatsuTaku/matsutaku-library

:heavy_check_mark: test/yosupo/yosupo-segment_add_get_min.test.cpp

Code

#define PROBLEM "https://judge.yosupo.jp/problem/segment_add_get_min"
#include "include/mtl/li_chao_tree.hpp"
#include "include/mtl/compress_int.hpp"
#include <bits/stdc++.h>
using namespace std;

int main() {
  int n,q; cin>>n>>q;
  vector<array<long long, 5>> Q(n+q);
  for (int i = 0; i < n; i++) {
    long long l,r,a,b; cin>>l>>r>>a>>b;
    Q[i] = {0,l,r,a,b};
  }
  Compressor<int> xcmp;
  for (int i = 0; i < q; i++) {
    int t; cin>>t;
    if (t == 0) {
      long long l,r,a,b; cin>>l>>r>>a>>b;
      Q[n+i] = {0, l, r, a, b};
    } else {
      int p; cin>>p;
      Q[n+i] = {1, p};
      xcmp.add(p);
    }
  }
  auto [xc,cx] = xcmp.release_tie();
  LiChaoTree<long long, greater<>> lct(cx.begin(), cx.end());
  for (int i = 0; i < n+q; i++) {
    if (Q[i][0] == 0) {
      long long l = Q[i][1], r = Q[i][2], a = Q[i][3], b = Q[i][4];
      lct.add_segment(a, b, l, r);
    } else {
      int p = Q[i][1];
      auto ans = lct.get(p);
      if (ans != LiChaoTree<long long, greater<>>::INF)
        cout << ans << endl;
      else
        cout << "INFINITY" << endl;
    }
  }
}
#line 1 "test/yosupo/yosupo-segment_add_get_min.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/segment_add_get_min"
#line 2 "include/mtl/bit_manip.hpp"
#include <cstdint>
#include <cassert>
#if __cplusplus >= 202002L
#ifndef MTL_CPP20
#define MTL_CPP20
#endif
#include <bit>
#endif

namespace bm {

/// Count 1s for each 8 bits
inline constexpr uint64_t popcnt_e8(uint64_t x) {
  x = (x & 0x5555555555555555) + ((x>>1) & 0x5555555555555555);
  x = (x & 0x3333333333333333) + ((x>>2) & 0x3333333333333333);
  x = (x & 0x0F0F0F0F0F0F0F0F) + ((x>>4) & 0x0F0F0F0F0F0F0F0F);
  return x;
}
/// Count 1s
inline constexpr unsigned popcnt(uint64_t x) {
#ifdef MTL_CPP20
  return std::popcount(x);
#else
  return (popcnt_e8(x) * 0x0101010101010101) >> 56;
#endif
}
/// Alias to mtl::popcnt(x)
constexpr unsigned popcount(uint64_t x) {
  return popcnt(x);
}
/// Count trailing 0s. s.t. *11011000 -> 3
inline constexpr unsigned ctz(uint64_t x) {
#ifdef MTL_CPP20
  return std::countr_zero(x);
#else
  return popcnt((x & (-x)) - 1);
#endif
}
/// Alias to mtl::ctz(x)
constexpr unsigned countr_zero(uint64_t x) {
  return ctz(x);
}
/// Count trailing 1s. s.t. *11011011 -> 2
inline constexpr unsigned cto(uint64_t x) {
#ifdef MTL_CPP20
  return std::countr_one(x);
#else
  return ctz(~x);
#endif
}
/// Alias to mtl::cto(x)
constexpr unsigned countr_one(uint64_t x) {
  return cto(x);
}
inline constexpr unsigned ctz8(uint8_t x) {
  return x == 0 ? 8 : popcnt_e8((x & (-x)) - 1);
}
/// [00..0](8bit) -> 0, [**..*](not only 0) -> 1
inline constexpr uint8_t summary(uint64_t x) {
  constexpr uint64_t hmask = 0x8080808080808080ull;
  constexpr uint64_t lmask = 0x7F7F7F7F7F7F7F7Full;
  auto a = x & hmask;
  auto b = x & lmask;
  b = hmask - b;
  b = ~b;
  auto c = (a | b) & hmask;
  c *= 0x0002040810204081ull;
  return uint8_t(c >> 56);
}
/// Extract target area of bits
inline constexpr uint64_t bextr(uint64_t x, unsigned start, unsigned len) {
  uint64_t mask = len < 64 ? (1ull<<len)-1 : 0xFFFFFFFFFFFFFFFFull;
  return (x >> start) & mask;
}
/// 00101101 -> 00111111 -count_1s-> 6
inline constexpr unsigned log2p1(uint8_t x) {
  if (x & 0x80)
    return 8;
  uint64_t p = uint64_t(x) * 0x0101010101010101ull;
  p -= 0x8040201008040201ull;
  p = ~p & 0x8080808080808080ull;
  p = (p >> 7) * 0x0101010101010101ull;
  p >>= 56;
  return p;
}
/// 00101100 -mask_mssb-> 00100000 -to_index-> 5
inline constexpr unsigned mssb8(uint8_t x) {
  assert(x != 0);
  return log2p1(x) - 1;
}
/// 00101100 -mask_lssb-> 00000100 -to_index-> 2
inline constexpr unsigned lssb8(uint8_t x) {
  assert(x != 0);
  return popcnt_e8((x & -x) - 1);
}
/// Count leading 0s. 00001011... -> 4
inline constexpr unsigned clz(uint64_t x) {
#ifdef MTL_CPP20
  return std::countl_zero(x);
#else
  if (x == 0)
    return 64;
  auto i = mssb8(summary(x));
  auto j = mssb8(bextr(x, 8 * i, 8));
  return 63 - (8 * i + j);
#endif
}
/// Alias to mtl::clz(x)
constexpr unsigned countl_zero(uint64_t x) {
  return clz(x);
}
/// Count leading 1s. 11110100... -> 4
inline constexpr unsigned clo(uint64_t x) {
#ifdef MTL_CPP20
  return std::countl_one(x);
#else
  return clz(~x);
#endif
}
/// Alias to mtl::clo(x)
constexpr unsigned countl_one(uint64_t x) {
  return clo(x);
}

inline constexpr unsigned clz8(uint8_t x) {
  return x == 0 ? 8 : 7 - mssb8(x);
}
inline constexpr uint64_t bit_reverse(uint64_t x) {
  x = ((x & 0x00000000FFFFFFFF) << 32) | ((x & 0xFFFFFFFF00000000) >> 32);
  x = ((x & 0x0000FFFF0000FFFF) << 16) | ((x & 0xFFFF0000FFFF0000) >> 16);
  x = ((x & 0x00FF00FF00FF00FF) << 8) | ((x & 0xFF00FF00FF00FF00) >> 8);
  x = ((x & 0x0F0F0F0F0F0F0F0F) << 4) | ((x & 0xF0F0F0F0F0F0F0F0) >> 4);
  x = ((x & 0x3333333333333333) << 2) | ((x & 0xCCCCCCCCCCCCCCCC) >> 2);
  x = ((x & 0x5555555555555555) << 1) | ((x & 0xAAAAAAAAAAAAAAAA) >> 1);
  return x;
}

/// Check if x is power of 2. 00100000 -> true, 00100001 -> false
constexpr bool has_single_bit(uint64_t x) noexcept {
#ifdef MTL_CPP20
  return std::has_single_bit(x);
#else
  return x != 0 && (x & (x - 1)) == 0;
#endif
}

/// Bit width needs to represent x. 00110110 -> 6
constexpr int bit_width(uint64_t x) noexcept {
#ifdef MTL_CPP20
  return std::bit_width(x);
#else
  return 64 - clz(x);
#endif
}

/// Ceil power of 2. 00110110 -> 01000000
constexpr uint64_t bit_ceil(uint64_t x) {
#ifdef MTL_CPP20
  return std::bit_ceil(x);
#else
  if (x == 0) return 1;
  return 1ull << bit_width(x - 1);
#endif
}

/// Floor power of 2. 00110110 -> 00100000
constexpr uint64_t bit_floor(uint64_t x) {
#ifdef MTL_CPP20
  return std::bit_floor(x);
#else
  if (x == 0) return 0;
  return 1ull << (bit_width(x) - 1);
#endif
}

} // namespace bm
#line 3 "include/mtl/li_chao_tree.hpp"
#include <utility>
#include <vector>
#include <limits>
#include <numeric>
#include <functional>
#include <cstring>
#include <iostream>

template<typename T, typename Comp = std::less<T>>
struct LiChaoTree {
  using Line = std::pair<T, T>;
  static constexpr T INF = std::numeric_limits<T>::max();
  static constexpr T MINF = std::numeric_limits<T>::min();
  static constexpr T INV = Comp()(MINF, INF) ? MINF : INF;
  size_t n, N;
  std::vector<T> X;
  std::vector<Line> seg;
  Comp cmp;

  LiChaoTree() = default;
  explicit LiChaoTree(size_t _n) : n(_n), N(_n ? 1ull<<(64-bm::clz(_n-1)) : 0), X(n), seg(N*2, {0, INV}) {
    std::iota(X.begin(), X.begin()+n, 0ull);
  }
  void set_x(size_t i, T x) {
    X[i] = x;
  }
  template<typename It>
  LiChaoTree(It begin, It end) : LiChaoTree(std::distance(begin, end)) {
    std::copy(begin, end, X.begin());
  }

 private:
  inline static T f(const Line& line, T x) {
    return line.first * x + line.second;
  }

  void _add_line(Line line, size_t u, size_t l, size_t r) {
    if (line.second == INV)
      return;
    auto mid = l + (r-l)/2;
    bool enabled_left = l < n and cmp(f(seg[u], X[l]), f(line, X[l]));
    bool enabled_mid = mid < n and cmp(f(seg[u], X[mid]), f(line, X[mid]));
    if (enabled_mid)
      std::swap(line, seg[u]);
    if (r-l == 1)
      return;
    if (enabled_left != enabled_mid)
      _add_line(line, u<<1, l, mid);
    else
      _add_line(line, (u<<1)|1u, mid, r);
  }
 public:
  void add_line(T a, T b) {
    _add_line({a, b}, 1, 0, N);
  }

  void add_segment_idx(T a, T b, size_t l, size_t r) {
    auto u = l+N, v = r+N;
    auto L = l, R = r;
    size_t range = 1;
    Line line{a,b};
    while (u < v) {
      if (u&1u) {
        _add_line(line, u++, L, L+range);
        L += range;
      }
      if (v&1u) {
        R -= range;
        _add_line(line, --v, R, R+range);
      }
      u >>= 1;
      v >>= 1;
      range <<= 1;
    }
    assert(L == R);
  }
  void add_segment(T a, T b, T xl, T xr) {
    assert(xl <= xr);
    auto xlit = std::lower_bound(X.begin(), X.end(), xl);
    auto xrit = std::lower_bound(xlit, X.end(), xr);
    add_segment_idx(a, b, xlit-X.begin(), xrit-X.begin());
  }

  T get_idx(T i) const {
    size_t u = i + N;
    T x = X[i];
    T ret = INV;
    while (u > 0) {
      auto v = f(seg[u], x);
      if (cmp(ret, v)) ret = v;
      u /= 2;
    }
    return ret;
  }
  T get(T x) const {
    auto it = std::lower_bound(X.begin(), X.end(), x);
    assert(it != X.end());
    return get_idx(it - X.begin());
  }
};
template<typename T, typename Comp>
constexpr T LiChaoTree<T, Comp>::INF;
template<typename T, typename Comp>
constexpr T LiChaoTree<T, Comp>::MINF;
template<typename T, typename Comp>
constexpr T LiChaoTree<T, Comp>::INV;
#line 2 "include/mtl/compress_int.hpp"
#include <set>
#include <unordered_map>
#line 5 "include/mtl/compress_int.hpp"
#include <algorithm>

template<class T, class MapContainer=std::unordered_map<T, int>>
class Compressor {
 public:
  using map_type = MapContainer;
 private:
  std::vector<T> vs;
 public:
  Compressor() = default;
  template<typename It>
  Compressor(It begin, It end) : vs(begin, end) {}
  void clear() { vs.clear(); }
  void add(T x) {
    vs.push_back(x);
  }
  template<typename It>
  void add(It begin, It end) {
    vs.insert(vs.end(), begin, end);
  }
  map_type release() {
    std::sort(vs.begin(), vs.end());
    vs.erase(std::unique(vs.begin(), vs.end()), vs.end());
    map_type mp;
    mp.reserve(vs.size());
    int k = 0;
    for (auto v : vs) mp[v] = k++;
    return mp;
  }
  std::pair<map_type, std::vector<T>> release_tie() {
    return std::make_pair(release(), std::move(vs));
  }
  template<typename It>
  static map_type compress(It begin, It end) {
    return Compressor(begin, end).release();
  }
};
#line 4 "test/yosupo/yosupo-segment_add_get_min.test.cpp"
#include <bits/stdc++.h>
using namespace std;

int main() {
  int n,q; cin>>n>>q;
  vector<array<long long, 5>> Q(n+q);
  for (int i = 0; i < n; i++) {
    long long l,r,a,b; cin>>l>>r>>a>>b;
    Q[i] = {0,l,r,a,b};
  }
  Compressor<int> xcmp;
  for (int i = 0; i < q; i++) {
    int t; cin>>t;
    if (t == 0) {
      long long l,r,a,b; cin>>l>>r>>a>>b;
      Q[n+i] = {0, l, r, a, b};
    } else {
      int p; cin>>p;
      Q[n+i] = {1, p};
      xcmp.add(p);
    }
  }
  auto [xc,cx] = xcmp.release_tie();
  LiChaoTree<long long, greater<>> lct(cx.begin(), cx.end());
  for (int i = 0; i < n+q; i++) {
    if (Q[i][0] == 0) {
      long long l = Q[i][1], r = Q[i][2], a = Q[i][3], b = Q[i][4];
      lct.add_segment(a, b, l, r);
    } else {
      int p = Q[i][1];
      auto ans = lct.get(p);
      if (ans != LiChaoTree<long long, greater<>>::INF)
        cout << ans << endl;
      else
        cout << "INFINITY" << endl;
    }
  }
}

Test cases

Env Name Status Elapsed Memory
g++ all_twice_00 :heavy_check_mark: AC 659 ms 37 MB
g++ example_00 :heavy_check_mark: AC 6 ms 3 MB
g++ example_01 :heavy_check_mark: AC 6 ms 3 MB
g++ max_random_00 :heavy_check_mark: AC 883 ms 28 MB
g++ max_random_01 :heavy_check_mark: AC 867 ms 28 MB
g++ max_random_02 :heavy_check_mark: AC 870 ms 28 MB
g++ random_00 :heavy_check_mark: AC 576 ms 22 MB
g++ random_01 :heavy_check_mark: AC 659 ms 23 MB
g++ random_02 :heavy_check_mark: AC 359 ms 15 MB
g++ small_00 :heavy_check_mark: AC 6 ms 3 MB
g++ small_01 :heavy_check_mark: AC 5 ms 3 MB
clang++ all_twice_00 :heavy_check_mark: AC 706 ms 37 MB
clang++ example_00 :heavy_check_mark: AC 6 ms 4 MB
clang++ example_01 :heavy_check_mark: AC 5 ms 4 MB
clang++ max_random_00 :heavy_check_mark: AC 862 ms 28 MB
clang++ max_random_01 :heavy_check_mark: AC 911 ms 28 MB
clang++ max_random_02 :heavy_check_mark: AC 873 ms 28 MB
clang++ random_00 :heavy_check_mark: AC 606 ms 22 MB
clang++ random_01 :heavy_check_mark: AC 630 ms 23 MB
clang++ random_02 :heavy_check_mark: AC 372 ms 15 MB
clang++ small_00 :heavy_check_mark: AC 6 ms 3 MB
clang++ small_01 :heavy_check_mark: AC 5 ms 3 MB
Back to top page