[ BOJ ][JAVA][20495] 수열과 헌팅

https://www.acmicpc.net/problem/20495

20495번: 수열과 헌팅

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	1024 MB	175	74	63	51.220%

문제

준원이는 여자친구를 만들 시나리오를 진지하게 세우고 있다.

먼저, 지나가던 아름다운 여성 분이 준원이에게 길이가 N인 수열 arr을 정렬해달라고 부탁한다. 그리고 준원이는 #include <algorithm>을 선언한 뒤 std::sort(arr, arr+N);을 사용해 시간복잡도 O(N log N)으로 멋지게 정렬해준다. 그리고, 사랑에 빠진다.

준원이는 실제로 이 상황에 마주친다. 하지만 그가 받은 수열은... 수열의 원소가 정해져 있지 않았다!

314 ± 25, 255 ± 140, ...

실제 수열의 각 원소는 받은 수열의 오차범위 내의 어떤 실수든 될 수 있다. 예를 들어, 첫번째 수인 314 ± 25는 314 - 25 = 289 이상 314 + 25 = 339 이하의 임의의 실수가 될 수 있다.

그녀는 길이 N의 수열 a1 ± b1, ..., aN ± bN을 준원이에게 주고, 수열을 정렬한 이후 각각의 수가 몇 번째에 가 있을지를 알고 싶다. 물론, 수열이 범위 안에서 어느 수로 결정되는가에 따라 답이 바뀔 수 있기 때문에, 각각의 수가 있을 수 있는 인덱스의 범위를 구하고 싶다. 만약 같은 수가 여러 개 있다면, 그 수들은 어떤 순서로 있든 무관하다. 준원이가 연애를 할 수 있도록, 여러분이 대신 그녀의 문제를 해결해 주자.

입력

첫째 줄에는 준원이가 받은 수열의 길이 N이 주어진다.

둘째 줄부터 N개의 줄에 걸쳐 준원이가 받은 수열이 주어진다. i번째 줄에는 준원이가 받은 수열의 i번째 원소 ai ± bi를 나타내는 두 정수 ai와 bi가 공백을 사이에 두고 주어진다.

출력

총 N개의 줄에 걸쳐서 출력한다. i번째 줄에는 수열을 정렬한 후, 수열의 i번째 원소가 있을 수 있는 인덱스의 최솟값과 최댓값을 공백을 사이에 두고 출력한다.

수열의 인덱스는 1부터 시작한다.

제한

• 2 ≤ N ≤ 500,000
• 각 1 ≤ i ≤ N에 대해, ai, bi는 정수이고, -109 ≤ ai ≤ 109, 0 ≤ bi ≤ 109.

예제 입력 1

3
10 20
40 15
70 15

예제 출력 1

1 2
1 3
2 3

코드

/*
    수열과 헌팅
    lower bound, upper bound

    어떤 원소가 최대한 앞에 나오기 위해서는 (1) 자기 자신은 최대한 작아지고, (2) 다른 모든 원소는 최대한 커져야 한다.
    마찬가지로, 어떤 원소가 최대한 뒤에 나오기 위해서는 (1) 자기 자신은 최대한 커지고, (2) 다른 모든 원소는 최대한 작아져야 한다.

    ai +- bi가 올 수 있는 가장 빠른 위치는 a[i] + b[i] 값을 다 모았을 때 a[x] - b[x]보다 작은 수의 개수
    ai +- bi가 올 수 있는 가장 느린 위치는 a[i] - b[i] 값을 다 모았을 때 a[x] + b[x]보다 작거나 같은 수의 개수 - 1
    따라서 이분탐색으로 진행해야 O(nlogn)에 답을 구할 수 있다.

    값의 범위는 2 * 10^9 이므로 int 범위 내에 있다.
*/
import java.io.*;
import java.util.*;
public class p20495 {
    static int n;
    static int[] l, r;
    static List<Integer> left, right;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 최대 N은 500,000 이고 넉넉히 선언한다.
        l = new int[505050];
        r = new int[505050];

        left = new ArrayList<>();
        right = new ArrayList<>();

        StringTokenizer st;
        n = Integer.parseInt(br.readLine());
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int ai = Integer.parseInt(st.nextToken());
            int bi = Integer.parseInt(st.nextToken());
            l[i] = ai - bi;
            r[i] = ai + bi;

            left.add(l[i]);
            right.add(r[i]);
        }
        Collections.sort(left);
        Collections.sort(right);

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append(lower_bound(right, l[i]) + 1).append(" ");
            sb.append(upper_bound(left, r[i])).append("\n");
        }

        System.out.println(sb.toString());
    }

    // lower bound는 찾고자 하는 값 이상이 처음 나타나는 위치
    static int lower_bound(List<Integer> list, int val) {
        int left = 0;
        int right = list.size();
        while (left < right) {
            int mid = (left + right) / 2;
            if (list.get(mid) >= val) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return right;
    }

    // upper bound는 찾고자 하는 값 이상이 처음 나타나는 위치
    static int upper_bound(List<Integer> list, int val) {
        int left = 0;
        int right = list.size();
        while (left < right) {
            int mid = (left + right) / 2;
            if (list.get(mid) <= val) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return right;
    }
}