結果

問題 No.2897 ２集合間距離
ユーザー 沙耶花沙耶花
提出日時 2024-09-20 21:40:14
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,882 ms / 3,500 ms
コード長 2,380 bytes
コンパイル時間 4,986 ms
コンパイル使用メモリ 271,776 KB
実行使用メモリ 137,984 KB
最終ジャッジ日時 2024-09-20 21:40:44
合計ジャッジ時間 21,358 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 94 ms
134,912 KB
testcase_01 AC 95 ms
134,784 KB
testcase_02 AC 94 ms
134,784 KB
testcase_03 AC 96 ms
134,912 KB
testcase_04 AC 97 ms
134,784 KB
testcase_05 AC 119 ms
134,912 KB
testcase_06 AC 95 ms
134,912 KB
testcase_07 AC 94 ms
134,912 KB
testcase_08 AC 94 ms
134,784 KB
testcase_09 AC 96 ms
134,784 KB
testcase_10 AC 97 ms
134,784 KB
testcase_11 AC 96 ms
134,784 KB
testcase_12 AC 104 ms
134,912 KB
testcase_13 AC 103 ms
134,912 KB
testcase_14 AC 162 ms
135,040 KB
testcase_15 AC 214 ms
135,040 KB
testcase_16 AC 1,882 ms
137,984 KB
testcase_17 AC 1,877 ms
137,984 KB
testcase_18 AC 1,881 ms
137,984 KB
testcase_19 AC 1,857 ms
137,856 KB
testcase_20 AC 1,873 ms
137,984 KB
testcase_21 AC 1,749 ms
137,856 KB
testcase_22 AC 1,619 ms
137,984 KB
testcase_23 AC 1,640 ms
137,984 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>
#include <atcoder/all>
#include <bits/stdc++.h>
using namespace std;
using namespace atcoder;
using mint = modint998244353;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define Inf32 1000000001
#define Inf64 4000000000000000001LL

template <class S, S (*op)(S, S), S (*e)()> struct _2d_segtree {
	
	vector<segtree<S,op,e>> seg;
	
	_2d_segtree() : _2d_segtree(0, 0) {
	}
	/*
	compressed_2d_segtree(vector<long long> tx, vector<S> v){
		_tx = tx;
		seg = segtree<S,op,e>(v);
	}
	*/
	_2d_segtree(int h,int w){
		if(h>w){
			swap(h,w);
			F = true;
		}
		int n = h;
		log = 0;
		while((1LL<<log) < n){
			log++;
		}
		
		size = 1<<log;
		
		seg.resize(size*2, segtree<S,op,e>(w));

	}
	
	void set(int px, int py, S x) {
		if(F)swap(px,py);
		px += size;
		seg[px].set(py,x);
        for (int i = 1; i <= log; i++) update(px >> i, py);
    }
	
	S get(int px,int py) {
		if(F)swap(px,py);
		return seg[px+size].get(py);
    }
	
	S prod(int lx,int rx,int ly,int ry) {
		if(F){
			swap(lx,ly);
			swap(rx,ry);
		}
		S sml = e(), smr = e();
        lx += size;
        rx += size;

        while (lx < rx) {
            if (lx & 1) sml = op(sml, seg[lx++].prod(ly,ry));
            if (rx & 1) smr = op(seg[--rx].prod(ly,ry), smr);
            lx >>= 1;
            rx >>= 1;
        }
        return op(sml, smr);
    }

	S all_prod() { return seg[1].all_prod(); }
	int size, log;
	bool F = false;
	void update(int k, int py) {
		seg[k].set(py, op(seg[2*k].get(py), seg[2*k+1].get(py)));
	}
};



long long op(long long a,long long b){
	return min(a,b);
}

long long e(){
	return (long long)Inf64;
}
int main(){
	
	int n;
	cin>>n;
	
	vector<pair<long long,long long>> tp(n);
	rep(i,n){
		cin>>tp[i].first>>tp[i].second;
	}
	_2d_segtree<long long,op,e> s00(1000,1000),s01(1000,1000),s10(1000,1000),s11(1000,1000);
	rep(i,n){
		s00.set(tp[i].first,tp[i].second,tp[i].first+tp[i].second);
		s01.set(tp[i].first,tp[i].second,tp[i].first-tp[i].second);
		s10.set(tp[i].first,tp[i].second,-tp[i].first+tp[i].second);
		s11.set(tp[i].first,tp[i].second,-tp[i].first-tp[i].second);
	}
	int m;
	cin>>m;
	long long ans = Inf64;
	rep(i,m){
		long long x,y;
		cin>>x>>y;
		ans = min(ans,s00.prod(x,1000,y,1000)-x-y);
		ans = min(ans,s01.prod(x,1000,0,y)-x+y);
		ans = min(ans,s10.prod(0,x,y,1000)+x-y);
		ans = min(ans,s11.prod(0,x,0,y)+x+y);
	}
	cout<<ans<<endl;
	
	return 0;
}
0