cp-includes

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

View the Project on GitHub rsalesc/cp-includes

:heavy_check_mark: tests/yosupo/segment-add-get-min.test.cpp

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/segment_add_get_min"

#include <bits/stdc++.h>
#include "ds/LiChaoTree.cpp"
#define int long long
using namespace std;
 
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ms(v, x) memset((v), (x), sizeof(v))
#define all(v) (v).begin(), (v).end()
#define ff first
#define ss second
#define iopt ios::sync_with_stdio(false); cin.tie(0)
#define untie(p, a, b) decltype(p.first) a = p.first, decltype(p.second) b = p.second
 
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a%b); }
int power(int x, int p, int MOD) {
    if(p == 0) return 1%MOD;
    if(p == 1) return x%MOD;
    int res = power(x, p/2, MOD);
    res = (long long)res*res%MOD;
    if(p&1) res = (long long)res*x%MOD;
    return res;
}
 
typedef pair<int, int> ii;
typedef long double LD;
typedef vector<int> vi;

struct Query {
  int type, a, b, l, r;
};

int32_t main(){
  iopt;
  
  int n, Q;
  cin >> n >> Q;

  vector<Query> queries;
  vector<int> xs;

  for(int i = 0; i < n; i++)  {
    int a, b, l, r; cin >> l >> r >> a >> b;
    queries.push_back({0, a, b, l, r});
  }

  for(int i = 0; i < Q; i++) {
    int t; cin >> t;
    if(t == 0) {
      int a, b, l, r; cin >> l >> r >> a >> b;
      queries.push_back({t, a, b, l, r});
    } else {
      int x; cin >> x;
      queries.push_back({t, x});
      xs.push_back(x);
    }
  }

  lib::LiChaoTree<int, int> t(xs);

  for(const auto& q : queries) {
    if (q.type == 0) {
      t.add_segment([q](int x) {
        return q.a * x + q.b;
      }, q.l, q.r);
    } else {
      auto res = t.query(q.a);
      if (res == decltype(t)::inf)
        cout << "INFINITY" << endl;
      else
        cout << res << endl;
    }
  }
}
#line 1 "tests/yosupo/segment-add-get-min.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/segment_add_get_min"

#include <bits/stdc++.h>
#line 1 "ds/LiChaoTree.cpp"



#line 5 "ds/LiChaoTree.cpp"

namespace lib {
using namespace std;

template <typename D, typename T> struct LiChaoTree {
  inline constexpr static T inf = numeric_limits<T>::max();

  using Fn = function<T(D)>;
  vector<Fn> fns;
  vector<D> xs;
  vector<int> t;

  template <typename U = D,
            typename enable_if<is_integral<U>::value>::type = nullptr>
  LiChaoTree(D left, D right) {
    assert(right > left);
    xs = vector<D>(right - left);
    iota(xs.begin(), xs.end(), left);
    init();
  }

  LiChaoTree(const vector<D>& xs_) : xs(xs_) {
    sort(xs.begin(), xs.end());
    xs.resize(unique(xs.begin(), xs.end()) - xs.begin());
    init();
  }

  void init() {
    t = vector<int>(xs.size() * 4);
    fns.clear();
    fns.push_back([](D x) { return numeric_limits<T>::max(); });
  }

  void add(const Fn &fn) {
    int i = fns.size();
    fns.push_back(fn);
    add(i, 1, 0, xs.size());
  }

  // r is exclusive
  void add(int i, int no, int l, int r) {
    while (1) {
      int mid = (l + r) / 2;
      bool l_wins = fns[i](xs[l]) < fns[t[no]](xs[l]);
      bool r_wins = fns[i](xs[r-1]) < fns[t[no]](xs[r-1]);
      if (l_wins == r_wins) {
        if (l_wins) swap(i, t[no]);
        return;
      }
      bool mid_wins = fns[i](xs[mid]) < fns[t[no]](xs[mid]);
      if (mid_wins)
        swap(i, t[no]);
      if (l + 1 == r)
        return;
      if (l_wins != mid_wins)
        no = 2 * no, r = mid;
      else
        no = 2 * no + 1, l = mid;
    }
  }

  int seg_l, seg_r, seg_idx;
  void add_segment(int no, int l, int r) {
    if (seg_l >= r || seg_r <= l) return;
    if (seg_l <= l && r <= seg_r) add(seg_idx, no, l, r);
    else {
      int mid = (l+r)/2;
      add_segment(2*no, l, mid);
      add_segment(2*no+1, mid, r);
    }
  }

  void add_segment(const Fn& fn, D a, D b) {
    int i = fns.size();
    fns.push_back(fn);
    int l = lower_bound(xs.begin(), xs.end(), a) - xs.begin();
    int r = lower_bound(xs.begin(), xs.end(), b) - xs.begin();
    if (l == r) return;
    seg_idx = i, seg_l = l, seg_r = r;
    add_segment(1, 0, xs.size());
  }

  T query(D x, int no, int l, int r) const {
    auto res = inf;
    while (1) {
      res = min(res, fns[t[no]](x));
      if (l + 1 == r)
        return res;
      int mid = (l + r) / 2;
      if (x < xs[mid])
        no = 2 * no, r = mid;
      else
        no = 2 * no + 1, l = mid;
    }
  }

  T query(D x) const { return query(x, 1, 0, xs.size()); }
};
} // namespace lib


#line 5 "tests/yosupo/segment-add-get-min.test.cpp"
#define int long long
using namespace std;
 
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ms(v, x) memset((v), (x), sizeof(v))
#define all(v) (v).begin(), (v).end()
#define ff first
#define ss second
#define iopt ios::sync_with_stdio(false); cin.tie(0)
#define untie(p, a, b) decltype(p.first) a = p.first, decltype(p.second) b = p.second
 
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a%b); }
int power(int x, int p, int MOD) {
    if(p == 0) return 1%MOD;
    if(p == 1) return x%MOD;
    int res = power(x, p/2, MOD);
    res = (long long)res*res%MOD;
    if(p&1) res = (long long)res*x%MOD;
    return res;
}
 
typedef pair<int, int> ii;
typedef long double LD;
typedef vector<int> vi;

struct Query {
  int type, a, b, l, r;
};

int32_t main(){
  iopt;
  
  int n, Q;
  cin >> n >> Q;

  vector<Query> queries;
  vector<int> xs;

  for(int i = 0; i < n; i++)  {
    int a, b, l, r; cin >> l >> r >> a >> b;
    queries.push_back({0, a, b, l, r});
  }

  for(int i = 0; i < Q; i++) {
    int t; cin >> t;
    if(t == 0) {
      int a, b, l, r; cin >> l >> r >> a >> b;
      queries.push_back({t, a, b, l, r});
    } else {
      int x; cin >> x;
      queries.push_back({t, x});
      xs.push_back(x);
    }
  }

  lib::LiChaoTree<int, int> t(xs);

  for(const auto& q : queries) {
    if (q.type == 0) {
      t.add_segment([q](int x) {
        return q.a * x + q.b;
      }, q.l, q.r);
    } else {
      auto res = t.query(q.a);
      if (res == decltype(t)::inf)
        cout << "INFINITY" << endl;
      else
        cout << res << endl;
    }
  }
}
Back to top page