인덱스국 선발고사 II (Team Selection II)

문제

인덱스국 선발고사 : Day 2

인덱스국의 선발고사는 항상 인덱스 트리 문제로 이루어져 있었으나, 인덱스국의 조교 앤디는 변화하는 국제 정세에 맞추어 이번에는 새로운 문제를 출제하기로 마음먹었습니다.

아래는 인덱스국의 왕 (검열됨)과 앤디가 SSHS MWT Slack에서 나눈 대화 내용의 일부입니 다.

(검열됨): 회의실 배정 문제는 어떤가?

(검열됨): 회의들의 시작 시간과 끝나는 시간들이 주어졌을 때, 최대 몇 개의 회의를 할 수 있는지 구하는 문제

앤디: 끝나는 시간과 시작하는 시간이 같은 두 회의는 둘 다 할 수 있나요?

(검열됨): ㅇㅇ

앤디: 저건 사람들이 인터넷에서 복붙할 수도 있지 않을까요? 네이버에 검색하면 너무 잘 나오는데

(잠시 정적)

(검열됨): 그럼 쿼리 줘

앤디: ??

(검열됨): 쿼리로 회의실이 열리는 시간과 닫히는 시간을 Q개 주고, 최대 몇 개의 회의를 할 수 있는지 구하는거임

앤디: 머지 걍 하면 되는거 아닌가요? 아닌가

(검열됨): 걍 하면 될듯 ㅋㅋㅋ

데이터를 만들기 위해 풀이를 구현해야 하는데, (검열됨)과 앤디는 인덱스 트리 문제 외에는 코딩해본 적이 없기 때문에, 코딩 자신감이 상당히 떨어져 있습니다. 코딩을 하고 싶지 않았던 그들은, 느린 알고리즘으로 모든 데이터를 만든 이후, 이를 선발고사에 내고, 학생들의 풀이를 베끼기로 했습니다.

구현 세부 사항

다음 함수들을 구현하세요.

void init(int S[], int E[])

• 이 함수는 처음 단 한 번 그레이더에 의해 호출됩니다.
• S, E는 크기 N의 배열입니다. 모든 0 ≤ i ≤ N − 1에 대해 i + 1번 회의가 S[i]에 시작해서 E[i]에 끝납니다.

int getMaximumMeetings(int X, int Y)

• 이 함수는 그레이더에 의해 Q번 호출됩니다.
• 이 함수는 회의실이 X에 열리고 Y에 닫힐 때 최대 회의의 개수를 반환해야 합니다.

제한 조건

• 1 ≤ N ≤ 500,000
• 1 ≤ Q ≤ 1,000,000
• 0 ≤ S[i] < E[i] ≤ 2,000,000 (0 ≤ i ≤ N − 1)
• 0 ≤ X < Y ≤ 2,000,000

서브태스크

서브태스크	점수	Q
1	2	Q ≤ 10
2	3	Q ≤ 500
3	10	Q ≤ 1,000,000

예제 입출력

N = 4, S = [1, 3, 5, 0], E = [4, 6, 8, 10]

그레이더는 다음 함수들을 호출합니다.

init([1, 3, 5, 0], [4, 6, 8, 10])

getMaximumMeetings(0, 15) = 2

getMaximumMeetings(1, 5) = 1

샘플 그레이더

Sample grader는 다음의 형식으로 입력을 받습니다.

• line 1 : N Q
• line 2 + i (0 ≤ i ≤ N − 1) : S[i] E[i]
• line 2 + M + i (0 ≤ i ≤ Q − 1) : X Y