Danciu: Pagină nouă: 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...

2024-06-04T08:23:59Z

Pagină nouă: 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...

New page

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>

4168 - Secvente 6 - Revision history