Editing 4168 - Secvente 6

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

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

Se dau <code>N</code> secvențe speciale de forma <code>[a, b]</code> și apoi <code>T</code> secvențe de interogare <code>[L,R]</code>. 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ță <code>[L, R]</code> le include va fi denumit capacitatea secvenței <code>[L, R]</code>.

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

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

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

= Restricții și precizări =

* <code>1 ≤ N ≤ 100.000</code>
* <code>1 ≤ a ≤ b ≤ 1.000.000.000</code>
* <code>1 ≤ T ≤ 100.000</code>
* <code>1 ≤ L ≤ R ≤ 1.000.000.000</code>

= Exemplu: =
<code>secvente.in</code>
 2
 2 4
 3 3
 3
 2 4
 1 5
 2 5
<code>secvente.out</code>
 4
 9
 6

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

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

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

== 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>