#905975 (C++14) No.2436 Min Diff Distance

提出ソース

結果

問題	No.2436 Min Diff Distance
ユーザー	蜜蜂
提出日時	2023-08-18 23:30:18
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	TLE
実行時間	-
コード長	9,262 bytes
コンパイル時間	5,166 ms
コンパイル使用メモリ	268,696 KB
実行使用メモリ	13,888 KB
最終ジャッジ日時	2024-05-06 06:17:31
合計ジャッジ時間	9,054 ms
ジャッジサーバーID （参考情報）	judge1 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 13,888 KB
testcase_01	AC	2 ms 6,816 KB
testcase_02	AC	2 ms 6,948 KB
testcase_03	TLE	-
testcase_04	--	-
testcase_05	--	-
testcase_06	--	-
testcase_07	--	-
testcase_08	--	-
testcase_09	--	-
testcase_10	--	-
testcase_11	--	-
testcase_12	--	-
testcase_13	--	-
testcase_14	--	-
testcase_15	--	-
testcase_16	--	-
testcase_17	--	-
testcase_18	--	-
testcase_19	--	-
testcase_20	--	-
testcase_21	--	-
testcase_22	--	-

権限があれば一括ダウンロードができます

コンパイルメッセージ

main.cpp: In member function 'uint32_t rectanglequery<T, S, op, e>::BitVectorRank::rank(uint32_t) const':
main.cpp:81:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
   81 |       auto [b, s] = a[i >> 6];
      |            ^
main.cpp: In function 'int main()':
main.cpp:337:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
  337 |     auto [x,y]=points[i];
      |          ^
main.cpp:342:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
  342 |     auto [x,y]=points[i];
      |          ^
main.cpp:350:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
  350 |       auto [x2,y2]=points[k];
      |            ^

ソースコード

raw source code

// g++-13 3.cpp -std=c++17 -O2 -I .
#include <bits/stdc++.h>
using namespace std;

#include <atcoder/all>
using namespace atcoder;

using ll = long long;
using ld = long double;
 
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vld = vector<ld>;
using vvld = vector<vld>;
using vst = vector<string>;
using vvst = vector<vst>;
 
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define pq_big(T) priority_queue<T,vector<T>,less<T>>
#define pq_small(T) priority_queue<T,vector<T>,greater<T>>
#define all(a) a.begin(),a.end()
#define rep(i,start,end) for(ll i=start;i<(ll)(end);i++)
#define per(i,start,end) for(ll i=start;i>=(ll)(end);i--)
#define uniq(a) sort(all(a));a.erase(unique(all(a)),a.end())

// https://nachiavivias.github.io/cp-library/cpp/multi-dimensional/two-d-rectangle-query.html
// https://github.com/NachiaVivias/cp-library/blob/main/Cpp/Include/nachia/multi-dimensional/two-d-rectangle-query.hpp
// https://judge.yosupo.jp/submission/139718
// https://atcoder.jp/contests/arc159/submissions/41442160

// T 座標の型
// S 点に乗せる型
// op 演算
// e 単位元
// 交換則,結合則は必要

template< typename T, typename S, S (*op)(S, S), S (*e)() >
struct rectanglequery{
private:
  struct BitVectorRank {
    using u64 = std::uint64_t;
    using u32 = std::uint32_t;

    static u32 popcountll(u64 c){
    #ifdef __GNUC__
      return __builtin_popcountll(c);
    #else
      c = (c & (~0ull/3)) + ((c >> 1) & (~0ull/3));
      c = (c & (~0ull/5)) + ((c >> 2) & (~0ull/5));
      c = (c & (~0ull/17)) + ((c >> 4) & (~0ull/17));
      c = (c * (~0ull/255)) >> 56;
      return c;
    #endif
    }
        
    std::vector<std::pair<u64, u32>> a;
    BitVectorRank(const std::vector<bool>& b = {}){
      int n = b.size();
      a.assign(n/64 + 1, std::make_pair((u64)0, (u32)0));
      auto p = b.begin();
      u32 sum = 0;
      u64 tmp = 0;
      for(int i=0; i<=n; i+=64){
        tmp = 0;
        int maxd = std::min<int>(n - i, 64);
        for(int d=0; d<maxd; d++){
          tmp |= (u64)(*p ? 1 : 0) << d;
          ++p;
        }
        a[i/64] = std::make_pair(tmp, sum);
        sum += popcountll(tmp);
      }
    }
    
    std::uint32_t rank(std::uint32_t i) const {
      auto [b, s] = a[i >> 6];
      return (u32)(popcountll(b & ~(~u64(0) << (i & 63)))) + s;
    }
    bool get(std::uint32_t i) const { return (a[i >> 6].first >> (i & 63)) & 1; }
  };

  struct BIT{
    vi A;
    BIT(int n=0){ A.assign(n+1,0); }
    int sum(int r){
        int res = 0;
        while(r){ res += A[r]; r -= r & -r; }
        return res;
    }
    void add(int p, int x){
        p += 1;
        while(p < A.size()){ A[p] += x; p += p & -p; }
    }
  };
  
  struct segmenttree{
    int _n;
    std::vector<S> node;
    
    segmenttree() = default;
    
    segmenttree(int n){
      _n=1;
      while(_n<n)_n*=2;
      node.resize(2*_n,e());
    }
    segmenttree(std::vector<S> &v){
      int n=v.size();
      _n=1;
      while(_n<n)_n*=2;
      node.resize(2*_n,e());
      for(int i=0;i<n;i++){
        set(i,v[i]);
      }
    }

    // [i] <- val
    void set(int i,S val){
      i+=_n;
      node[i]=val;
      while(i>1){
        i>>=1;
        node[i]=op(node[2*i],node[2*i+1]);
      }
    }

    // [i] <- op([i],val)
    void update(int i,S val){
      i+=_n;
      node[i]=op(node[i],val);
      while(i>1){
        i>>=1;
        node[i]=op(node[2*i],node[2*i+1]);
      }
    }

    S get(int i){
      i+=_n;
      return node[i];
    }

    S prod(int l,int r){
      S pdl=e(),pdr=e();
      l+=_n;r+=_n;

      while(l<r){
        if(l&1)pdl=op(pdl,node[l++]);
        if(r&1)pdr=op(node[--r],pdr);
        l>>=1;r>>=1;
      }

      return op(pdl,pdr);
    };
  };
  
  int n;
  int N;
  int logN;
  std::vector<T> Xsorted;
  std::vector<T> Ysorted;
  std::vector<int> rankX;
  std::vector<std::vector<int>> Idx;
  std::vector<int> Z;
  std::vector<BitVectorRank> L;
  std::vector<BIT> seg;
  std::map<std::pair<T,T>,int> index;

public:
  
  rectanglequery(const std::vector<std::pair<T,T>> &points){
    n=points.size();

    for(int i=0;i<n;i++)index[points[i]]=i;

    std::vector<int> sortIY(n);
    for(int i=0;i<n;i++)sortIY[i]=i;
    std::sort(sortIY.begin(),sortIY.end(),[&points](int l,int r){return points[l].second<points[r].second;});
    Ysorted.resize(n);
    for(int i=0;i<n;i++)Ysorted[i]=points[sortIY[i]].second;

    std::vector<int> sortIX(n);
    rankX.resize(n);
    for(int i=0;i<n;i++)sortIX[i]=i;
    std::sort(sortIX.begin(),sortIX.end(),[&points](int l,int r){ return points[l]<points[r];});
    Xsorted.resize(n);
    for(int i=0;i<n;i++)Xsorted[i]=points[sortIX[i]].first;
    for(int i=0;i<n;i++)rankX[sortIX[i]]=i;

    N=1;logN=0;
    while(N<n){N*=2;logN++;}
    Idx.assign(logN+1,std::vector<int>(n,-1));
    L.resize(logN);
    Z.resize(logN);
    for(int i=0;i<n;i++)Idx.back()[i]=sortIY[i];
    for(int i=logN-1;i>=0;i--){
    std::vector<bool> Lbuf(n,0);
    auto& preList = Idx[i+1];
    int z=((n>>(i+1))<<i)+std::min(1<<i,(n%(2<<i)));
    Z[i]=z;
    int ai=0,bi=z;
    for(int k=0;k<n;k++){
      bool chooseb=rankX[preList[k]]&(1<<i);
      if(!chooseb)Idx[i][ai++]=preList[k];
      else Idx[i][bi++]=preList[k];
      Lbuf[k]=!chooseb;
      }
      L[i]=BitVectorRank(Lbuf);
    }
    
    for(int i=0;i<n;i++)rankX[sortIY[i]]=i;

    seg.resize(Idx.size());
    for(int i=0;i<Idx.size();i++){
      seg[i]=BIT(n+1);
    }
  }

  int get_segment_count() const {return Idx.size();}
  int size() const {return n;}
  int to_vtx(int d,int i) const {return Idx[d][i];} 

  struct UpdatePoint{ int d, i; };

    std::vector<UpdatePoint> get_update_points(int v) const {
        std::vector<UpdatePoint> res(logN+1);
        int p = rankX[v];
        int d = logN;
        while(d > 0){
            res[d] = { d,p };
            d--;
            if(L[d].get(p)) p = L[d].rank(p);
            else p = Z[d] + p - L[d].rank(p);
        }
        res[d] = {d,p};
        return res;
    }


    struct Query{ int d,l,r; };
    std::vector<Query> get_ranges_from_idx(int xl, int xr, int yl, int yr){
        std::vector<Query> res;
        struct Search{ int i, xa, xb, ys, yt; };
        std::vector<Search> Q;
        res.reserve((logN+1)*2);
        Q.reserve((logN+1)*2);
        Q.push_back({ logN,0,n,yl,yr });
        for(int i=0; i<(int)Q.size(); i++){
            auto p = Q[i];
            if(p.xa == p.xb) continue;
            if(xr <= p.xa || p.xb <= xl) continue;
            if(xl <= p.xa && p.xb <= xr){
                res.push_back({ p.i, p.ys, p.yt });
                continue;
            }
            p.i--;
            int nxs = L[p.i].rank(p.ys), nxt = L[p.i].rank(p.yt);
            Q.push_back({ p.i,p.xa,p.xa+(1<<p.i),nxs,nxt });
            Q.push_back({ p.i,p.xa+(1<<p.i),p.xb,Z[p.i]+p.ys-nxs,Z[p.i]+p.yt-nxt });
        }
        return res; 
    }
  
    std::vector<Query> get_ranges(T xl, T xr, T yl, T yr){
        return get_ranges_from_idx(
            lower_bound(Xsorted.begin(),Xsorted.end(),xl) - Xsorted.begin(),
            lower_bound(Xsorted.begin(),Xsorted.end(),xr) - Xsorted.begin(),
            lower_bound(Ysorted.begin(),Ysorted.end(),yl) - Ysorted.begin(),
            lower_bound(Ysorted.begin(),Ysorted.end(),yr) - Ysorted.begin()
        );
    }

  //////  

  // point <- val
  void point_set(T px,T py,S val){
    int ind=index[{px,py}];
    for(auto qq:this->get_update_points(ind)){
      seg[qq.d].add(qq.i,val);
    }
  }

  // point <- op(point,val)
  void point_update(T px,T py,S val){
    int ind=index[{px,py}];
    for(auto qq:this->get_update_points(ind)){
      seg[qq.d].add(qq.i,val);
    }
  }

  S query(T x_mn,T x_mx,T y_mn,T y_mx){
    S res=e();
    for(auto qq:this->get_ranges(x_mn,x_mx,y_mn,y_mx)){
      res=op(res,seg[qq.d].sum(qq.r)-seg[qq.d].sum(qq.l));
    }
    return res;
  }
};



int op(int a,int b){
  return a+b;
}
int e(){
  return (int)0;
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  auto start=clock();

  int n;cin>>n;
  vector<pair<int,int>> points(n);
  rep(i,0,n){
    int x,y;cin>>x>>y;
    x--;y--;
    points[i]={x+y,x-y};
  }

  rep(i,0,2*n-1){
    points.emplace_back(i,-(n-1)+i);
  }


  rectanglequery<int,int,op,e> rec(points);


  int ans=4e6;
  rep(i,0,n){
    auto [x,y]=points[i];
    rec.point_set(x,y,1);
  }

  rep(i,0,n){
    auto [x,y]=points[i];

    int ng1=0,ok1=5e5,ng2=0,ok2=5e5;
    
    rep(j,0,10){
      if(n<100)break;
      int k=i+j;
      if(k>=n)k-=n;
      auto [x2,y2]=points[k];
      int d=max(abs(x-x2),abs(y-y2));
      ok1=min(ok1,d);
      ng2=max(ng2,d-1);
    }

    while(ok1-ng1>1){
      int c=(ok1+ng1)/2;
      int q=rec.query(x-c,x+c+1,y-c,y+c+1);
      if(q==1){
        ng1=c;
      }
      else{
        ok1=c;
      }
    }

    while(ok2-ng2>1){
      int c=(ok2+ng2)/2;
      int q=rec.query(x-c,x+c+1,y-c,y+c+1);
      if(q==n){
        ok2=c;
      }
      else{
        ng2=c;
      }
    }

    //cout<<ng1<<" "<<ok1<<" "<<ng2<<" "<<ok2<<endl;

    ans=min(ans,ok2-ok1);
  }

  cout<<ans<<endl;

  auto end=clock();

  cout<<fixed<<setprecision(5);
  cerr<<(double)(end-start)/(CLOCKS_PER_SEC)<<endl;
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード