| Fişierul intrare/ieşire: | calafat.in, calafat.out | Sursă | ONI 2016, clasele 11-12 |
| Autor | Denis-Gabriel Mita | Adăugată de |  Andrei Constantinescu •Andrei1998 |
| Timp execuţie pe test | 0.75 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Calafat
Această problemă se numeşte Calafat pentru că a fost compusă în timpul excursiei la Calafat de mâine.
Cerinta
Se dă un şir format din N numere naturale. Pentru fiecare valoare distinctă dintr-o subsecvenţă cuprinsă între 2 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
Pe prima linie a fişierului de intrare calafat.in se vor afla două numere natural N şi M. Pe a doua linie se vor afla cele N numere din sirul 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
În fişierul de ieşire calafat.out se vor afişa M numere naturale, câte unul pe fiecare linie, reprezentând
cele M sume cerute.
Restricţii
- 1 ≤ N, M ≤ 200 000
- 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 | calafat.out |
|---|---|
| 7 3 1 3 1 2 2 1 3 2 4 2 7 3 6 | 0 9 4 |
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.
