문제 5292 · 킬로 I

붐비는 할인 일수

인증 제출 통계 · 5분마다 갱신 · 정답 비율 = 정답 제출 / 전체 제출
시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1000ms / 테스트 (언어별 보정은 아래 표)	메모리: 측정하지 않음(브라우저 채점)	0	0	0	0.00%

문제

온라인 쇼핑몰은 1일부터 N일까지 할인 행사를 운영한다. 행사는 모두 M개이며, i번째 행사는 l_i일부터 r_i일까지 양 끝 날짜를 포함해 매일 진행된다. 행사 기간은 서로 겹쳐도 되고 완전히 같아도 된다. 어떤 날에 동시에 진행되는 행사의 수가 K개 이상이면 그날을 붐비는 날이라고 부른다. 진행되는 행사가 K개 미만이면 붐비는 날이 아니다. 운영팀은 점검할 날짜 구간 Q개를 정해 두었다. j번째 점검 구간은 a_j일부터 b_j일까지이며 양 끝 날짜를 포함한다. 운영팀은 각 구간 안에 붐비는 날이 며칠 있는지 알고 싶다. 붐비는 날이 하나도 없으면 0을 출력한다. 모든 값은 정수이다. 행사 수와 질의 수가 많으므로 질의마다 날짜를 하나씩 훑으면 시간이 부족할 수 있다. 각 질의의 답을 입력 순서대로 구하는 프로그램을 작성하시오.

입력

첫 줄에 N, M, K, Q가 공백으로 구분되어 주어진다. (1 ≤ N ≤ 200,000, 1 ≤ M ≤ 12,000, 1 ≤ K ≤ 200,000, 1 ≤ Q ≤ 12,000) 다음 M개의 줄에 각각 l_i와 r_i가 주어진다. (1 ≤ l_i ≤ r_i ≤ N) 다음 Q개의 줄에 각각 a_j와 b_j가 주어진다. (1 ≤ a_j ≤ b_j ≤ N)

출력

각 질의에 대한 붐비는 날의 수를 한 줄에 하나씩 순서대로 출력한다.

예제 입력 1

예제 출력 1

4
2
0

예제 입력 2

1 1 1 1
1 1
1 1

예제 출력 2

힌트 펼치기

행사 구간마다 차이 배열에 +1, -1을 기록한 뒤 누적하면 날짜별 행사 수가 나온다.
붐비는 날을 1, 아니면 0으로 둔 배열의 누적 합을 만들면 구간 질의가 O(1)이다.

풀이 작성

연습 채점은 공개 테스트로 실행합니다. 인증 제출은 코드를 봉인한 뒤 새 입력을 실행하고 서버에서 출력을 대조하며 코드와 판정을 저장합니다.

풀이를 제출하면 여기에서 결과를 확인할 수 있습니다.

연습 기록은 이 브라우저에 최근 50개를 저장합니다. 인증 기록은 내 제출에서 확인하세요.

이 브라우저의 연습 기록

언어별 제한

테스트 케이스마다 새 전역에서 실행하며 준비 시간은 제외합니다. 시간 초과된 출력은 검사하지 않습니다. 브라우저·기기 성능에 따라 실행 시간이 달라집니다.

언어	엔진(버전)	시간 제한	메모리
javascript	사용자 브라우저 JavaScript 엔진 (버전은 브라우저에 따라 다름)	1000ms / 테스트	측정하지 않음(브라우저 채점)
python	Pyodide 314.0.7 (CPython 3.14 WASM)	5000ms / 테스트	측정하지 않음(브라우저 채점)

문제

입력

출력