백준17423 민원이 넘쳐흘러

작성일 | In

문제 링크

  • http://icpc.me/17423

문제 출처

  • 2019 선린 정올 5번

사용 알고리즘

  • 스위핑
  • 좌표압출
  • 세그먼트 트리 with 레이지 프로퍼게이션
  • 이분탐색

시간복잡도

  • \[O(N log N log 1e6)\]

풀이

지금껏 풀어왔던 문제를 합친 느낌입니다.

먼저 BOJ2496 금강석(풀이)처럼 맵을 45도 회전시켜 각 직사각형의 변들이 x, y축에 평행하도록 만들어줍니다.

이제 최대 볼륨을 찾기 위해서 이분 탐색을 하는데, 결정 문제를 풀기 위해서 몇 가지를 처리해야 합니다.

  1. 현재 볼륨으로 인해 확장된 직사각형의 왼쪽/오른쪽/위/아래 좌표들을 모아서 압축을 해줍니다. 이 과정을 거치면 x, y좌표가 각각 40만 이하로 압축이 돼서 세그먼트 트리를 만들어도 메모리가 안전합니다.
  2. BOJ3392 화성지도비슷하게 스위핑을 해주면서 겹치는 구간이 있는지 판단을 해줍니다.

1번 과정에서 \(O(N log N)\), 2번 과정에서도 \(O(N log N)\), 이런 결정 문제를 \(O(log 1e6)\)번 풀어야 하기 때문에 \(O(N log N log 1e6)\)에 풀 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
# pragma GCC optimize ("O3")
# pragma GCC optimize ("Ofast")
# pragma GCC optimize ("unroll-loops")
# pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
#include <bits/stdc++.h>
#define y1 WHO_DEFINE_Y1_IN_HEADER
#define all(v) v.begin(), v.end()
using namespace std;

typedef long long ll;
typedef pair<int, int> p;

int tree[2020202], tmp[2020202];

void push(int node, int s, int e){
	if(!tmp[node]) return;
	tree[node] += (e-s+1) * tmp[node];
	if(s ^ e){
		tmp[node*2] += tmp[node];
		tmp[node*2+1] += tmp[node];
	}
	tmp[node] = 0;
}

void update(int node, int s, int e, int l, int r, int v){
	push(node, s, e);
	if(r < s || e < l) return;
	if(l <= s && e <= r){
		tree[node] += (e-s+1) * v;
		if(s ^ e){
			tmp[node*2] += v;
			tmp[node*2+1] += v;
		}
		return;
	}
	int m = s + e >> 1;
	update(node*2, s, m, l, r, v);
	update(node*2+1, m+1, e, l, r, v);
	tree[node] = tree[node*2] + tree[node*2+1];
}

int query(int node, int s, int e, int l, int r){
	push(node, s, e);
	if(r < s || e < l) return 0;
	if(l <= s && e <= r) return tree[node];
	int m = s + e >> 1;
	return query(node*2, s, m, l, r) + query(node*2+1, m+1, e, l, r);
}

int n;
ll s[101010], x[101010], y[101010];

vector<ll> compX, compY;
vector<p> up[404040], down[404040], pos[404040];

void init(){
	memset(tree, 0, sizeof tree);
	memset(tmp, 0, sizeof tmp);
	compX.clear(); compY.clear();
	for(int i=0; i<404040; i++){
		up[i].clear();
		down[i].clear();
		pos[i].clear();
	}
}

void pre(ll mid){
	for(int i=1; i<=n; i++){
		ll d = mid * s[i];
		ll x1 = x[i] - d, x2 = x[i] + d;
		ll y1 = y[i] - d, y2 = y[i] + d;
		if(y1 > y2) swap(y1, y2);
		compX.push_back(x1);
		compX.push_back(x2);
		compY.push_back(y1);
		compY.push_back(y2);
		compY.push_back(y1+1);
		compY.push_back(y2-1);
	}
	sort(all(compX)); sort(all(compY));
	compX.erase(unique(all(compX)), compX.end());
	compY.erase(unique(all(compY)), compY.end());
	for(int i=1; i<=n; i++){
		ll d = mid * s[i];
		ll x1 = lower_bound(all(compX), x[i]-d) - compX.begin() + 1;
		ll x2 = lower_bound(all(compX), x[i]+d) - compX.begin() + 1;
		ll y1 = lower_bound(all(compY), y[i]-d) - compY.begin() + 1;
		ll y2 = lower_bound(all(compY), y[i]+d) - compY.begin() + 1;
		if(y1 > y2) swap(y1, y2);
		up[x1].push_back({y1, y2});
		down[x2].push_back({y1, y2});
		pos[x1].push_back({y1, y2});
		pos[x2].push_back({y1, y2});
	}
}

bool chk(ll mid){
	init(); pre(mid);
	for(int i=0; i<404040; i++){
		for(auto t : down[i]){
			update(1, 1, 404040, t.first, t.second, -1);
		}
		for(auto t : pos[i]){
			ll res = query(1, 1, 404040, t.first+1, t.second-1);
			if(res > 0) return 0;
		}
		for(auto t : up[i]){
			update(1, 1, 404040, t.first, t.second, 1);
		}
	}
	return 1;
}

signed main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	for(int i=1; i<=n; i++) cin >> s[i];
	for(int i=1; i<=n; i++){
		ll a, b; cin >> a >> b;
		x[i] = a + b; y[i] = a - b;
	}
	ll l = 0, r = 1010101, ans = -1;
	while(l <= r){
		ll m = l + r >> 1;
		if(chk(m)){
			ans = m; l = m + 1;
		}else{
			r = m - 1;
		}
	}
	cout << ans;
}