test MinLineContainer
(test/aoj/3069.test.cpp)

• View this file on GitHub
• Last update: 2020-10-27 12:29:50+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3069

Depends on

• convexhulltrick/linecontainer.cpp
• tools/chminmax.cpp

Code

// verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3069

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

#define call_from_test
#include "../../tools/chminmax.cpp"
#include "../../convexhulltrick/linecontainer.cpp"
#undef call_from_test

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

  using ll = long long;
  int n,m,q;
  cin>>n>>m>>q;

  vector<ll> ds(n);
  for(int i=0;i<n;i++) cin>>ds[i];
  for(int i=0;i<n;i++) ds.emplace_back(int(ds[i]));
  for(int i=0;i<n;i++) ds.emplace_back(int(ds[i]));

  vector<ll> sm(n*3+1,0);
  for(int i=0;i<n*3;i++) sm[i+1]=sm[i]+ds[i];

  vector<char> cs(m);
  vector<int> bs(m),ts(m);
  for(int i=0;i<m;i++) cin>>cs[i]>>bs[i]>>ts[i],bs[i]--;

  vector< vector<ll> > G(n*3);
  vector<ll> xs(q),ys(q);
  for(int i=0;i<q;i++){
    cin>>xs[i]>>ys[i];
    xs[i]--,ys[i]--;
    xs[i]+=n,ys[i]+=n;
    G[xs[i]].emplace_back(i);
  }

  const ll INF = 1e18;
  vector<ll> R(n*3,INF),L(n*3,INF);
  int exR=0,exL=0;
  for(int i=0;i<m;i++){
    if(cs[i]=='R'){
      exR=1;
      chmin(R[bs[i]+n*0],ts[i]);
      chmin(R[bs[i]+n*1],ts[i]);
      chmin(R[bs[i]+n*2],ts[i]);
    }
    if(cs[i]=='L'){
      exL=1;
      chmin(L[bs[i]+n*0],ts[i]);
      chmin(L[bs[i]+n*1],ts[i]);
      chmin(L[bs[i]+n*2],ts[i]);
    }
  }

  vector<ll> ans(q,INF);

  // use R
  if(exR){
    MinLineContainer<ll> cht;
    for(int x=0;x<n*2;x++){
      if(R[x]!=INF) cht.add(R[x],-R[x]*sm[x]);
      for(int i:G[x]){
        int y=ys[i];
        if(x>y) y+=n;
        chmin(ans[i],cht.query(sm[y]));
      }
    }
  }

  // use L
  if(exL){
    MinLineContainer<ll> cht;
    for(int x=n*3-1;x>=n;x--){
      if(L[x]!=INF) cht.add(-L[x],L[x]*sm[x]);
      for(int i:G[x]){
        int y=ys[i];
        if(x<y) y-=n;
        chmin(ans[i],cht.query(sm[y]));
      }
    }
  }

  for(int i=0;i<q;i++) cout<<ans[i]<<'\n';
  return 0;
}

#line 1 "test/aoj/3069.test.cpp"
// verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3069

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

#define call_from_test
#line 1 "tools/chminmax.cpp"

#line 3 "tools/chminmax.cpp"
using namespace std;
#endif
//BEGIN CUT HERE
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
//END CUT HERE
#ifndef call_from_test
signed main(){
  return 0;
}
#endif
#line 1 "convexhulltrick/linecontainer.cpp"

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

template<typename T>
struct Line {
  mutable T k,m,p;
  bool operator<(const Line&o)const{return k<o.k;}
  bool operator<(T x)const{return p<x;}
};

template<typename T> T lc_inf(){return numeric_limits<T>::max();}
template<> double lc_inf<double>(){return 1/.0;}

template<typename T> T lc_div(T a,T b){return a/b-((a^b)<0 and a%b);}
template<> double lc_div(double a,double b){return a/b;};

template<typename T, Objective objective>
struct LineContainer : multiset<Line<T>, less<>>{
  using super = multiset<Line<T>, less<>>;
  using super::begin,super::end,super::insert,super::erase;
  using super::empty,super::lower_bound;
  const T inf = lc_inf<T>();
  bool insect(typename super::iterator x,typename super::iterator y){
    if(y==end()) return x->p=inf,false;
    if(x->k==y->k) x->p=(x->m>y->m?inf:-inf);
    else x->p=lc_div(y->m-x->m,x->k-y->k);
    return x->p>=y->p;
  }
  void add(T k,T m){
    auto z=insert({k*objective,m*objective,0}),y=z++,x=y;
    while(insect(y,z)) z=erase(z);
    if(x!=begin() and insect(--x,y)) insect(x,y=erase(y));
    while((y=x)!=begin() and (--x)->p>=y->p) insect(x,erase(y));
  }
  T query(T x){
    assert(!empty());
    auto l=*lower_bound(x);
    return (l.k*x+l.m)*objective;
  }
};
template<typename T>
using MinLineContainer = LineContainer<T, Objective::MINIMIZE>;
template<typename T>
using MaxLineContainer = LineContainer<T, Objective::MAXIMIZE>;
//END CUT HERE

#ifndef call_from_test
//INSERT ABOVE HERE
signed main(){
  return 0;
}
#endif
#line 9 "test/aoj/3069.test.cpp"
#undef call_from_test

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

  using ll = long long;
  int n,m,q;
  cin>>n>>m>>q;

  vector<ll> ds(n);
  for(int i=0;i<n;i++) cin>>ds[i];
  for(int i=0;i<n;i++) ds.emplace_back(int(ds[i]));
  for(int i=0;i<n;i++) ds.emplace_back(int(ds[i]));

  vector<ll> sm(n*3+1,0);
  for(int i=0;i<n*3;i++) sm[i+1]=sm[i]+ds[i];

  vector<char> cs(m);
  vector<int> bs(m),ts(m);
  for(int i=0;i<m;i++) cin>>cs[i]>>bs[i]>>ts[i],bs[i]--;

  vector< vector<ll> > G(n*3);
  vector<ll> xs(q),ys(q);
  for(int i=0;i<q;i++){
    cin>>xs[i]>>ys[i];
    xs[i]--,ys[i]--;
    xs[i]+=n,ys[i]+=n;
    G[xs[i]].emplace_back(i);
  }

  const ll INF = 1e18;
  vector<ll> R(n*3,INF),L(n*3,INF);
  int exR=0,exL=0;
  for(int i=0;i<m;i++){
    if(cs[i]=='R'){
      exR=1;
      chmin(R[bs[i]+n*0],ts[i]);
      chmin(R[bs[i]+n*1],ts[i]);
      chmin(R[bs[i]+n*2],ts[i]);
    }
    if(cs[i]=='L'){
      exL=1;
      chmin(L[bs[i]+n*0],ts[i]);
      chmin(L[bs[i]+n*1],ts[i]);
      chmin(L[bs[i]+n*2],ts[i]);
    }
  }

  vector<ll> ans(q,INF);

  // use R
  if(exR){
    MinLineContainer<ll> cht;
    for(int x=0;x<n*2;x++){
      if(R[x]!=INF) cht.add(R[x],-R[x]*sm[x]);
      for(int i:G[x]){
        int y=ys[i];
        if(x>y) y+=n;
        chmin(ans[i],cht.query(sm[y]));
      }
    }
  }

  // use L
  if(exL){
    MinLineContainer<ll> cht;
    for(int x=n*3-1;x>=n;x--){
      if(L[x]!=INF) cht.add(-L[x],L[x]*sm[x]);
      for(int i:G[x]){
        int y=ys[i];
        if(x<y) y-=n;
        chmin(ans[i],cht.query(sm[y]));
      }
    }
  }

  for(int i=0;i<q;i++) cout<<ans[i]<<'\n';
  return 0;
}

Back to top page