CSES - Datatähti 2020 alku - Lukuvälit
  • Time limit: 1.00 s
  • Memory limit: 512 MB
Sinulle annetaan joukko lukuvälejä ja tehtäväsi on määrittää jokaisesta, monessako välin kokonaisluvussa jokainen numero on $0$ tai $1$.

Syöte

Ensimmäisellä rivillä on yksi kokonaisluku $n$: lukuvälien määrä.

Tämän jälkeen syötteessä on $n$ riviä, joista kullakin on kaksi kokonaislukua $a$ ja $b$: tutkittavana on lukuväli $[a,b]$.

Tuloste

Tulosta jokaisen kyselyn vastaus omalle rivilleen.

Esimerkki

Syöte:
4
0 10
1 5
3 4
11 11


Tuloste:
3
1
0
1


Selitys: Esimerkiksi välillä $[0,10]$ on kolme halutunlaista lukua: $0$, $1$ ja $10$.

Osatehtävä 1 (12 pistettä)
  • $1 \leq n \leq 1000$
  • $0 \leq a \leq b \leq 1000$
Osatehtävä 2 (24 pistettä)
  • $1 \leq n \leq 10^5$
  • $0 \leq a \leq b \leq 10^5$
Osatehtävä 3 (64 pistettä)
  • $1 \leq n \leq 10^5$
  • $0 \leq a \leq b \leq 10^{18}$