루미 알고리즘

#1547플래티넘Solar System

PO 2022 온라인 예선코딩출제 Johan Sannemo, Abdullah Zaghmout영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

The planets in a solar system have entered into a number of very complicated customs unions. Each customs union consists of a continuous interval of planets, where the customs union [a, b] consists of all planets between the a-th and b-th, counted from the sun.

Your friend Zorgax runs a large logistics company that handles interplanetary transports. Every time the company makes a transport between two planets, they must go through a customs process for each customs union they enter or exit between the two planets. However, if a certain customs union lies strictly between the start and end points of the journey, the transport does not have to go through that customs union; they simply fly over all the planets that are part of that union.

For each transport, Zorgax must first determine which entry and exit processes the transport must undergo. This is very time-consuming, so he has asked for your help.

Zorgax has planned Q different trips, where each trip goes between two planets. For each planned trip, print the number of entry and exit customs processes the transport must undergo.

Input

The first line contains the number of customs unions N (1 ≤ N ≤ 10^5).

This is followed by N lines, one for each customs union. The i-th of these contains two integers, 1 ≤ l_i ≤ r_i ≤ 10^9. This means there is a customs union that consists of all planets j where l_i ≤ j ≤ r_i, where the planets are numbered according to their distance from the sun.

Next, there is a line with the number of planned trips Q (1 ≤ Q ≤ 10^5).

Finally, there are Q lines, one for each trip. Each line consists of two integers 1 ≤ a ≠ b ≤ 10^9 – the planets from which the trip starts and ends, respectively.

Output

Print a single integer for each trip – the number of entry and exit customs processes the transport must undergo.

Scoring

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.

GroupPointsConstraints
115Q=1
235l_i ≤ l_{i + 1} and r_i ≤ r_{i+1} for all i.
338a,b,r_i ≤ 10^5
412No additional constraints.

Explanation of Sample 2

In example case 2, there are five customs unions. Of these, planet 1 is part of the first and fourth unions, and planet 10 is part of the first and fifth unions. The trip between planet 1 and 10 thus requires two customs processes: first when the transport leaves planet 1 and the fourth union, and another when it arrives at planet 10 and enters the fifth union. The second and third unions lie strictly between the two planets, so the transport never needs to enter either of these unions. Therefore, the answer is 2.

예제

예제 1

입력
2
1 3
2 3
1
3 1
출력
1

예제 2

입력
5
1 10
2 4
6 7
1 9
2 10
2
1 10
7 3
출력
2
2

예제 3

입력
4
4 10
7 11
14 14
18 22
3
10 2
3 8
11 20
출력
2
2
2

예제 4

입력
5
4 7
16 18
14 16
7 13
2 10
3
3 8
11 20
4 7
출력
1
1
1

출처 표기

출처: Programmeringsolympiaden 2022년 온라인 예선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.