Hide

Solsystem

Planeterna i ett solsystem har ingått ett antal mycket komplicerade tullunioner. Varje tullunion består av ett kontinuerligt intervall av planeter, där tullunionen $[a, b]$ består av alla planeter mellan den $a$:te och den $b$:te, räknat från solen.

Din kompis Zorgax driver ett stort logistikföretag som sköter interplanetära transporter. Varje gång företaget gör en transport mellan två planeter måste de genomgå en förtullningsprocess för varje tullunion som de lämnar eller åker in i mellan de två planeterna. Om en viss tullunion ligger strikt mellan resans startpunkt och slutpunkt behöver transporten dock inte åka genom denna tullunion; man flyger över alla planeter som ingår i den unionen, helt enkelt.

Vid varje transport måste Zorgax först ta reda på vilka inrese- respektive utreseprocesser transporten måste utföra. Detta är mycket tidskrävande, så hen har bett om din hjälp.

Zorgax har planterat $Q$ olika resor, där varje resa går mellan två planeter. För varje planerad resa, skriv ut antalet inrese- respektive utresetullprocesser som transporten måste genomgå.

Indata

Den första raden innehåller antalet tullunioner $N$ ($1 \le N \le 10^5$).

Sedan följer $N$ rader, en för varje tullunion. Den $i$:te av dessa innehåller två heltal, $1 \le l_ i \leq r_ i \le 10^9$. Detta betyder det finns en tullunionen som består av alla planeter $j$ där $l_ i \leq j \leq r_ i$, där planeterna är numrerade efter deras avstånd från solen.

Därefter följer en rad med antalet planerade resor $Q$ ($1 \le Q \le 10^5$).

Till sist följer $Q$ rader, en för varje resa. Varje rad består av två heltal $1 \le a \neq b \le 10^9$ – de planeter som resan startar från respektive slutar på.

Utdata

Skriv ut ett heltal för varje resa – antalet inrese- respektive utresetullprocesser transporten måste genomgå.

Poängsättning

Din lösning kommer att testas på ett antal testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

Grupp

Poängvärde

Gränser

$1$

$15$

$Q=1$

$2$

$35$

för alla $i$ gäller att $l_ i \le l_{i + 1}$ och $r_ i \le r_{i+1}$

$3$

$38$

$ a,b,r_ i \leq 10^5$

$4$

$12$

Inga ytterligare begränsningar

Notera att vissa exempelfall är inte giltiga i vissa testfallsgrupper.

Förklaringar av exempelfall

I exempelfall $2$ finns det fem tullunioner. Av dessa är planet $1$ med i den första och den fjärde, och planet $10$ i den första och den femte. Resan mellan planet $1$ och $10$ kräver alltså två tullprocesser: först en när transporten lämnar planet $1$ och den fjärde unionen, och en när den ankommer till planet $10$ och åker in i den femte unionen. Den andra och tredje unionen ligger strikt emellan de två planeterna, så transporten behöver aldrig åka in i någon av unionerna. Svaret är därför $2$.

Sample Input 1 Sample Output 1
2
1 3
2 3
1
3 1
1
Sample Input 2 Sample Output 2
5
1 10
2 4
6 7
1 9
2 10
2
1 10
7 3
2
2
Sample Input 3 Sample Output 3
4
4 10
7 11
14 14
18 22
3
10 2
3 8
11 20
2
2
2
Sample Input 4 Sample Output 4
5
4 7
16 18
14 16
7 13
2 10
3
3 8
11 20
4 7
1
1
1
CPU Time limit 6 seconds
Memory limit 1024 MB
Authors
Johan Sannemo and Abdullah Zaghmout
Source Programmeringsolympiadens onlinekval 2022
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in