BOJ 20495 - 수열과 헌팅
인덱스 가 최소값이 되려면 번째 구간에선 가장 최소값이고 나머지들은 모두 최대값이 되어야 하고 최대값이 되려면 반대로 그 구간에선 최대값이고 다른 구간들은 모두 최소값이 되어야 한다.
최소값 최대값을 따로 구분해서 정렬해서 이분탐색으로 특정 수가 몇번째에 들어가는지 처리해주면 에 문제를 해결할 수 있다.
가 가능해서 헷갈릴 수도 있지만 그 경우에도 lower_bound 와 upper_bound의 동작을 잘 생각해보면 따로 처리할 것이 없음을 알 수 있다.
최소값을 구하는 경우 lower_bound는 보다 작은것들은 건너뛰고 와 같은 것중 가장 작은 위치를 반환받게 되고
최대값을 구하는 경우 upper_bound 는 보다 큰것들 중 가장 작은 인덱스를 반환받게 된다. 그런데 최소값들의 집합에서는 항상 가 포함이 되어있을 것이므로 을 해준다.
void solve () {
int n;
cin >> n;
vector<pi> a (n);
for (auto &[x, y] : a) cin >> x >> y;
vi L, R;
for (auto &[x, y] : a) L.pb (x - y), R.pb (x + y);
sort (all (L));
sort (all (R));
for (int i = 0; i < n; i++) {
int lowest = a[i].fi - a[i].se;
int highest = a[i].fi + a[i].se;
cout << lbi (R, lowest) + 1 << ' ' << ubi (L, highest) << endl;
}
}
Comments