Fişierul intrare/ieşire:calafat.in, calafat.outSursăONI 2016, clasele 11-12
AutorDenis-Gabriel MitaAdăugată deAndrei1998Constantinescu Andrei-Costin Andrei1998
Timp execuţie pe test1.5 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/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.incalafat.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.
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?