AjM: Pagină nouă: == Enunt == Această problemă se numește Calafat pentru că a fost compusă în timpul excursiei la Calafat de mâine. == Cerinţa == Se dă un șir format din N numere naturale. Pentru fiecare valoare distinctă dintr-o subsecvență cuprinsă între doi indici st si dr considerăm distanța dintre indicii primei și ultimei apariții ale acesteia în cadrul subsecvenței. Dându-se M subsecvențe de forma [st, dr], se cere să se calculeze suma distanțelor corespunzătoa...

2024-06-03T16:48:28Z

Pagină nouă: == Enunt == Această problemă se numește Calafat pentru că a fost compusă în timpul excursiei la Calafat de mâine. == Cerinţa == Se dă un șir format din N numere naturale. Pentru fiecare valoare distinctă dintr-o subsecvență cuprinsă între doi indici st si dr considerăm distanța dintre indicii primei și ultimei apariții ale acesteia în cadrul subsecvenței. Dându-se M subsecvențe de forma [st, dr], se cere să se calculeze suma distanțelor corespunzătoa...

New page

== Enunt ==
Această problemă se numește Calafat pentru că a fost compusă în timpul excursiei la Calafat de mâine.
== Cerinţa ==
Se dă un șir format din N numere naturale. Pentru fiecare valoare distinctă dintr-o subsecvență cuprinsă între doi indici st si dr considerăm distanța dintre indicii primei și ultimei apariții ale acesteia în cadrul subsecvenței. Dându-se M subsecvențe de forma [st, dr], se cere să se calculeze suma distanțelor corespunzătoare tuturor valorilor distincte din subsecvență.
== Date de intrare ==
Fișierul de intrare calafat.in conține pe prima linie două numere natural N și M. Pe a doua linie se vor afla cele N numere din șirul dat. Pe următoarele M linii se vor afla câte două numere st și dr, cu semnificația că vrem să calculăm suma menționată mai sus pentru subsecvența [st,dr].
== Date de ieșire ==
Fișierul de ieșire calafat.out va conține M numere naturale, câte unul pe fiecare linie, reprezentând cele M sume cerute.
== Restricţii şi precizări ==
* 1 ≤ N, M ≤ 200000
* 1 ≤ st ≤ dr ≤ N
* Valorile din șir se vor afla în intervalul [1, N]
* Pentru 20% din teste se garantează că N, M ≤ 1000
* Pentru alte 25% din teste se garantează că N, M ≤ 35 000 iar numărul de elemente distincte din șir este maxim 100.
* Pentru alte 25% din teste se garantează că N, M ≤ 70 000
== Exemplu ==
; calafat.in
7 3
1 3 1 2 2 1 3
2 4
2 7
3 6
; calafat.out
0
9
4
<br>

== Explicație ==
În prima subsecvență fiecare valoare apare o singură dată, deci suma diferențelor este 0.

În a doua subsecvență:

* Valoarea 3 apare la indicii 2 și 7 rezultând diferența 7-2=5
* Valoarea 1 apare la indicii 3 și 6 => diferența 6–3=3
* Valoarea 2 apare la indicii 4 și 5 => diferența 5-4=1
Suma diferențelor este 9.

În a treia subsecvență:

* Valoarea 1 apare la indicii 3 și 6 => diferența 6–3=3
* Valoarea 2 apare la indicii 4 și 5 => diferența 5-4=1
Suma diferențelor este 4.
== Rezolvare ==
<syntaxhighlight lang="python" line>
def main():
with open("calafat.in", "r") as fin:
N, M = map(int, fin.readline().split())
sequence = list(map(int, fin.readline().split()))
queries = [tuple(map(int, line.split())) for line in fin.readlines()]

with open("calafat.out", "w") as fout:
for query in queries:
st, dr = query
subsequence = sequence[st-1:dr]
distinct_values = set(subsequence)
result = calculate_distances(subsequence, distinct_values)
fout.write(str(result) + "\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

1692 - Calafat - Revision history