結果
| 問題 | No.2436 Min Diff Distance |
| ユーザー |
 蜜蜂
|
| 提出日時 | 2023-08-18 23:33:00 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 9,262 bytes |
| コンパイル時間 | 4,698 ms |
| コンパイル使用メモリ | 268,680 KB |
| 実行使用メモリ | 164,248 KB |
| 最終ジャッジ日時 | 2024-05-06 06:20:41 |
| 合計ジャッジ時間 | 8,573 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
10,752 KB |
| testcase_01 | AC | 2 ms
5,376 KB |
| testcase_02 | AC | 1 ms
5,376 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];
| ^
ソースコード
// 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,20){
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;
}