4168 - Secvente 6

Notăm cu [x, y], o secvență de numere naturale nenule x, x + 1, x + 2, ..., y, cu x ≤ y.

Considerăm că secvența [p, q] include secvența [a, b] dacă are loc relația p ≤ a ≤ b ≤ q.

Se dau N secvențe speciale de forma [a, b] și apoi T secvențe de interogare [L,R]. Orice secvență care include cel puțin o secvență specială va fi numită secvență super-specială. Numărul de secvențe super-speciale pe care o secvență [L, R] le include va fi denumit capacitatea secvenței [L, R].

Cerința

Pentru fiecare secvență de interogare, să se determine capacitatea sa.

Date de intrare

Fișierul de intrare secvente.in conține pe prima linie numărul natural N, reprezentând numărul de secvențe speciale. Pe următoarele N linii se află câte două numere naturale nenule a și b, separate printr-un spațiu, reprezentând secvențele speciale. Pe linia N+2 se află numărul natural T, reprezentând numărul de secvențe de interogare, iar pe următoarele T linii se află câte două numere naturale nenule L și R, separate printr-un spațiu, reprezentând secvențele de interogare.

Date de ieșire

Fișierul de ieșire secvente.out va conține T linii. Pe cea de a i-a linie din fișier se va scrie un singur număr natural, reprezentând capacitatea celei de a i-a secvențe de interogare, în ordinea din fișierul de intrare.

Restricții și precizări

• 1 ≤ N ≤ 100.000
• 1 ≤ a ≤ b ≤ 1.000.000.000
• 1 ≤ T ≤ 100.000
• 1 ≤ L ≤ R ≤ 1.000.000.000

Exemplu:

secvente.in

2
2 4
3 3
3
2 4
1 5
2 5

secvente.out

4
9
6

Explicație

Secvența de interogare [2,4] conține secvențele super-speciale [2,3], [2,4], [3,3] și [3,4]. Se observă că [2, 2] nu este o secvență super-specială deoarece nu include pe niciuna dintre cele două secvențe speciale ([2, 4] și [3, 3]).

Secvența de interogare [1,5] conține secvențele super-speciale [1,3], [1,4], [1,5], [2,3], [2,4], [2,5], [3,3], [3,4] și [3,5].

Secvența de interogare [2,5] conține secvențele super-speciale [2,3], [2,4], [2,5], [3,3], [3,4] și [3,5].

Rezolvare

<syntaxhighlight lang="python3"> def read_special_sequences(n):

   special_sequences = []
   for _ in range(n):
       a, b = map(int, input().split())
       special_sequences.append((a, b))
   return special_sequences

def read_query_sequences(t):

   query_sequences = []
   for _ in range(t):
       l, r = map(int, input().split())
       query_sequences.append((l, r))
   return query_sequences

def is_super_special(query_sequence, special_sequences):

   for a, b in special_sequences:
       if a <= query_sequence[0] <= query_sequence[1] <= b:
           return True
   return False

def count_super_special_sequences(query_sequence, special_sequences):

   count = 0
   for a, b in special_sequences:
       if a <= query_sequence[0] <= b <= query_sequence[1]:
           count += 1
   return count

def main():

   n = int(input())
   special_sequences = read_special_sequences(n)

   t = int(input())
   query_sequences = read_query_sequences(t)

   for query_sequence in query_sequences:
       super_special_count = count_super_special_sequences(query_sequence, special_sequences)
       print(super_special_count)

if __name__ == "__main__":

   main()

</syntaxhighlight>