test/yosupo/line_add_get_min.test.cpp

• View this file on GitHub
• Last update: 2020-11-22 19:37:49+09:00
• Problem: https://judge.yosupo.jp/problem/line_add_get_min

Depends on

• convexhulltrick/segmentcontainer.cpp

Code

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

#include<bits/stdc++.h>
using namespace std;

#define call_from_test
#include "../../convexhulltrick/segmentcontainer.cpp"
#undef call_from_test

#ifdef SANITIZE
#define IGNORE
#endif

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);

  using ll = long long;
  int n,q;
  cin>>n>>q;
  vector<ll> as(n),bs(n);
  for(int i=0;i<n;i++) cin>>as[i]>>bs[i];

  vector<ll> ts(q),xs(q),ys(q);
  vector<ll> ps;
  for(int i=0;i<q;i++){
    cin>>ts[i];
    if(ts[i]==0) cin>>xs[i]>>ys[i];
    if(ts[i]==1) cin>>xs[i];
    ps.emplace_back(xs[i]);
  }
  int lb=-1e9,ub=+1e9;
  ps.emplace_back(lb);
  ps.emplace_back(ub);
  MinSegmentContainer<ll> seg(ps);

  for(int i=0;i<n;i++) seg.add(as[i],bs[i],lb,ub);
  for(int i=0;i<q;i++){
    if(ts[i]==0) seg.add(xs[i],ys[i],lb,ub);
    if(ts[i]==1) cout<<seg.query(xs[i])<<"\n";
  }
  return 0;
}

#line 1 "test/yosupo/line_add_get_min.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/line_add_get_min"

#include<bits/stdc++.h>
using namespace std;

#define call_from_test
#line 1 "convexhulltrick/segmentcontainer.cpp"

#line 3 "convexhulltrick/segmentcontainer.cpp"
using namespace std;
#endif
//BEGIN CUT HERE
enum Objective{
  MINIMIZE = +1,
  MAXIMIZE = -1,
};

template <typename T,Objective objective>
struct SegmentContainer{
  const T INF = numeric_limits<T>::max() / 2;
  struct Segment{
    T a,b;
    T operator()(T x) const{return a*x+b;}
  };

  int n;
  vector<T> xs;
  vector<Segment> dat;
  SegmentContainer(const vector<T> &xs_):xs(xs_){
    sort(xs.begin(),xs.end());
    xs.erase(unique(xs.begin(),xs.end()),xs.end());
    n=xs.size();
    dat.assign(n<<1,Segment({T(0),INF}));
  }

  inline int index(T x) const{
    return lower_bound(xs.begin(),xs.end(),x)-xs.begin();
  }

  // [xl, xr)
  void add(T a,T b,T xl,T xr){
    Segment g({a*objective,b*objective});
    for(int l=index(xl)+n,r=index(xr)+n;l<r;l>>=1,r>>=1){
      if(l&1) update(g,l++);
      if(r&1) update(g,--r);
    }
  }

  void update(Segment g,int i){
    int l=i,r=i+1;
    while(l<n) l<<=1,r<<=1;
    while(l<r){
      int m=(l+r)>>1;
      T xl=xs[l-n],xr=xs[r-1-n],xm=xs[m-n];
      Segment &f=dat[i];
      if(f(xl)<=g(xl) and f(xr)<=g(xr)) return;
      if(f(xl)>=g(xl) and f(xr)>=g(xr)) return (void)(f=g);
      if(f(xm)>g(xm)) swap(f,g);
      if(f(xl)>g(xl)) i=(i<<1)|0,r=m;
      else i=(i<<1)|1,l=m;
    }
  }

  T query(T x){
    T res=INF;
    for(int i=index(x)+n;i;i>>=1) res=min(res,dat[i](x));
    return res*objective;
  }
};
template<typename T>
using MinSegmentContainer = SegmentContainer<T, Objective::MINIMIZE>;
template<typename T>
using MaxSegmentContainer = SegmentContainer<T, Objective::MAXIMIZE>;
//END CUT HERE
#ifndef call_from_test
//INSERT ABOVE HERE
signed main(){
  return 0;
}
#endif
#line 8 "test/yosupo/line_add_get_min.test.cpp"
#undef call_from_test

#ifdef SANITIZE
#define IGNORE
#endif

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);

  using ll = long long;
  int n,q;
  cin>>n>>q;
  vector<ll> as(n),bs(n);
  for(int i=0;i<n;i++) cin>>as[i]>>bs[i];

  vector<ll> ts(q),xs(q),ys(q);
  vector<ll> ps;
  for(int i=0;i<q;i++){
    cin>>ts[i];
    if(ts[i]==0) cin>>xs[i]>>ys[i];
    if(ts[i]==1) cin>>xs[i];
    ps.emplace_back(xs[i]);
  }
  int lb=-1e9,ub=+1e9;
  ps.emplace_back(lb);
  ps.emplace_back(ub);
  MinSegmentContainer<ll> seg(ps);

  for(int i=0;i<n;i++) seg.add(as[i],bs[i],lb,ub);
  for(int i=0;i<q;i++){
    if(ts[i]==0) seg.add(xs[i],ys[i],lb,ub);
    if(ts[i]==1) cout<<seg.query(xs[i])<<"\n";
  }
  return 0;
}

Back to top page