結果

問題 No.2248 max(C)-min(C)
コンテスト
ユーザー eQe
提出日時 2025-09-29 01:00:06
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 526 ms / 3,000 ms
コード長 6,031 bytes
コンパイル時間 3,733 ms
コンパイル使用メモリ 300,284 KB
実行使用メモリ 49,508 KB
最終ジャッジ日時 2025-09-29 01:00:26
合計ジャッジ時間 18,842 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 51
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#if __has_include(<atcoder/all>)
#endif
using namespace std;
#define eb emplace_back
#define done(...) return pp(__VA_ARGS__)
#define LL(...) ll __VA_ARGS__;lin(__VA_ARGS__)
#define RDVL(T,n,...) vec<T>__VA_ARGS__;fe(refs(__VA_ARGS__),e)e.get().resizes(n);lin(__VA_ARGS__)
#define VL(n,...) RDVL(ll,n,__VA_ARGS__)
#define fo(i,...) for(auto[i,i##stop,i##step]=for_range<ll>(0,__VA_ARGS__);i<i##stop;i+=i##step)
#define of(i,...) for(auto[i,i##stop,i##step]=for_range<ll>(1,__VA_ARGS__);i>=i##stop;i+=i##step)
#define fe(a,e,...) for(auto&&__VA_OPT__([)e __VA_OPT__(,__VA_ARGS__]):a)
#define binary_operator(op,type) auto operator op(const type&rhs)const{auto copy=*this;return copy op##=rhs;}
#define defpp template<ostream&o=cout>void pp(const auto&...a){[[maybe_unused]]const char*c="";((o<<c<<a,c=" "),...);o<<'\n';}void epp(const auto&...a){pp<cerr>(a...);}
#define entry defpp void main();void main2();}int main(){my::io();my::main();}namespace my{
namespace my{
void io(){cin.tie(nullptr)->sync_with_stdio(0);cout<<fixed<<setprecision(15);}
using ll=long long;
constexpr auto refs(auto&...a){return array{ref(a)...};}
template<class T>constexpr auto for_range(T s,T b){T a=0;if(s)swap(a,b);return array{a-s,b,1-s*2};}
template<class T>constexpr auto for_range(T s,T a,T b,T c=1){return array{a-s,b,(1-s*2)*c};}
void lin(auto&...a){(cin>>...>>a);}
constexpr ll size2(auto x){x|=1;ll r=0;while(x>0)x>>=1,++r;return r;}
constexpr ll size10(auto x){x|=1;ll r=0;while(x>0)x/=10,++r;return r;}
template<class T>constexpr ll maxsize10(){return size10(numeric_limits<T>::max());}
bool amin(auto&a,const auto&b){return b<a?a=b,1:0;}
template<class A,class B=A>struct pair{
  A a;B b;
  pair()=default;
  pair(A aa,B bb):a(aa),b(bb){}
  auto operator<=>(const pair&)const=default;
};
template<bool is_negative=false>struct infinity{
  template<integral T>static constexpr T ones(size_t n){return n?ones<T>(n-1)*10+1:0;}
  template<integral T>constexpr operator T()const{static constexpr T v=ones<T>(maxsize10<T>())*(1-is_negative*2);return v;}
  template<class T>constexpr bool operator==(const T&x)const{return static_cast<T>(*this)==x;}
  constexpr auto operator-()const{return infinity<!is_negative>();}
};
constexpr infinity oo;
template<class F=less<>>auto&sort(auto&a,F f={}){ranges::sort(a,f);return a;}
auto&unique(auto&a){sort(a).erase(ranges::unique(a).begin(),a.end());return a;}
template<class...A>using pack_back_t=tuple_element_t<sizeof...(A)-1,tuple<A...>>;
}
namespace my{
template<class V>istream&operator>>(istream&i,vector<V>&v){fe(v,e)i>>e;return i;}
template<class V>constexpr int depth=0;
template<class T>struct core_t_helper{using type=T;};
template<class T>using core_t=core_t_helper<T>::type;
template<class V>struct vec;
template<int D,class T>struct hvec_helper{using type=vec<typename hvec_helper<D-1,T>::type>;};
template<class T>struct hvec_helper<0,T>{using type=T;};
template<int D,class T>using hvec=hvec_helper<D,T>::type;
template<class V>struct vec:vector<V>{
  static constexpr int D=depth<V>+1;
  using C=core_t<V>;
  using vector<V>::vector;
  void resizes(const auto&...a){if constexpr(sizeof...(a)==D)*this=make(a...,C{});else{ }}
  static auto make(ll n,const auto&...a){
    if constexpr(sizeof...(a)==1)return vec<C>(n,array{a...}[0]);
    else { }
  }
  auto&operator^=(const vec&u){this->insert(this->end(),u.begin(),u.end());return*this;}
  binary_operator(^,vec)
  ll size()const{return vector<V>::size();}
  auto&emplace_back(auto&&...a){vector<V>::emplace_back(std::forward<decltype(a)>(a)...);return*this;}
  auto lower_bound(const V&x)const{return std::lower_bound(this->begin(),this->end(),x);}
  ll arg_lower_bound(const V&x)const{return lower_bound(x)-this->begin();}
};
template<class...A>requires(sizeof...(A)>=2)vec(const A&...a)->vec<hvec<sizeof...(A)-2,pack_back_t<A...>>>;
auto zip(auto&...a){auto v=(a^...);unique(v);([&](auto&u){fe(u,e)e=v.arg_lower_bound(e);}(a),...);return v;}
}
namespace my{
namespace sgt{
template<class S,S op(S,S),S e()>struct segtree{
  int n,N,log;
  vector<S>d;
  explicit segtree(const vector<S>&v):n(int(v.size())){
    log=size2(n);
    N=1<<log;
    d=vector<S>(2*N,e());
    fo(i,n)d[N+i]=v[i];
    of(i,N,1)update(i);
  }
  void update(int k){d[k]=op(d[2*k],d[2*k+1]);}
  void set(int p,S x){
    assert(0<=p&&p<n);
    p+=N;
    d[p]=x;
    for(int i=1;i<=log;i++)update(p>>i);
  }
  S prod(int l,int r)const{
    assert(0<=l&&l<=r&&r<=n);
    S sml=e(),smr=e();
    l+=N;
    r+=N;
    while(l<r){
      if(l&1)sml=op(sml,d[l++]);
      if(r&1)smr=op(d[--r],smr);
      l>>=1;
      r>>=1;
    }
    return op(sml,smr);
  }
  S exclude_prod(int i)const{return op(prod(0,i),prod(i+1,n));}
  S all_prod()const{return d[1];}
};
template<class T,auto x>T identity(){return x;}
template<class T>T max(T a,T b){return a<b?b:a;}
template<class T>struct segmax:segtree<T,max<T>,identity<T,-oo>>{
  using segtree<T,max<T>,identity<T,-oo>>::segtree;
};
}
}
namespace my{entry
void main(){
  LL(N);
  VL(N,a,b);
  if(N==1)done(0);

  vec<ll>m(N);
  fo(i,N){
    if(a[i]>b[i])swap(a[i],b[i]);
    m[i]=(a[i]+b[i])/2;
  }

  auto val=zip(a,m,b);
  ll M=val.size();
  vec<vec<pair<ll,ll>>>g(M);
  fo(i,N){
    if(a[i]==m[i]){
      if(m[i]==b[i])g[b[i]].eb(i,2);
      else{
        g[m[i]].eb(i,1);
        g[b[i]].eb(i,2);
      }
    }else{
      if(m[i]==b[i]){
        m[i]=a[i];
        g[m[i]].eb(i,2);
        g[b[i]].eb(i,2);
      }
      else{
        g[a[i]].eb(i,0);
        g[m[i]].eb(i,1);
        g[b[i]].eb(i,2);
      }
    }
  }

  sgt::segmax<ll>s(a); // 各iについて,mi以上の最小のc_iの候補をin-placeに更新

  ll ans=oo;
  fo(mi,M){ // 最小値を固定
    if(s.all_prod()==oo)break; // あるiについて,mi以上の最小のc_iの候補がなくなったらcを作れないので終了
    fe(g[mi],i,f)amin(ans,val[s.exclude_prod(i)]-val[mi]);

    fe(g[mi],i,f){
      if(f==0)s.set(i,m[i]);
      else if(f==1)s.set(i,b[i]);
      else if(f==2)s.set(i,oo);
    }
  }
  pp(ans);
}}
0