Blog

SUM UNICE

Anul trecut de ziua ta ai primit un șir de n numere întregi. Anul acesta ai noroc: pe lângă un șir de numere întregi a1, a2, …, an mai primești și un număr natural k. Numim cadoul unei secvențe din șir de lungime k numărul elementelor care apar o singură dată în secvență. De exemplu, dacă a=(1,2,1,3,5) și k=4, atunci cadoul secvenței (1,2,1,3) este 2 (numerele 2 și 3 apar o singură dată), iar cadoul secvenței (2,1,3,5) este 4.

Cerința

Trebuie să determini suma cadourilor tuturor secvențelor de lungime k din șir și vei mai primi cadou două bilete la teatru și o carte motivațională.

Date de intrare

Programul citește de la tastatură numerele naturale n și k, iar apoi n numere naturale, separate prin spații, reprezentând șirul.

Date de ieșire

Programul va afișa pe ecran numărul C, reprezentând suma cadourilor tuturor secvențelor.

Restricții și precizări

  • 5 ≤ n ≤ 123.456
  • 1 ≤ k ≤ n
  • -1.000.000.000 ≤ ai ≤ 1.000.000.000

Exemplu

Intrare

7 4
1 2 3 3 3 3 4

Ieșire

4

Explicație

Prima secvență de lungime 4 este (1,2,3,3) și are cadoul egal cu 2.
A doua secvență de lungime 4 este (2,3,3,3) și are cadoul egal cu 1.
A treia secvență de lungime 4 este (3,3,3,3) și are cadoul egal cu 0.
A patra secvență de lungime 4 este (3,3,3,4) și are cadoul egal cu 1.
Suma cadourilor este deci 4.

SOLUTIE

#include <bits/stdc++.h>

using namespace std;
unordered_map<int,int>mp;
int v[130000];
int main()
{
    int n,k,cnt=0,total=0;
    cin>>n>>k;;
    for(int i=0;i<n;i++)
    cin>>v[i];
    for(int i=0;i<k;i++)
    {
          mp[v[i]]++;
          if(mp[v[i]]==1)cnt++;
          if(mp[v[i]]==2)cnt--;
    }
    total=cnt;
    for(int i=k;i<n;i++)
    {
          mp[v[i-k]]--;
          if(mp[v[i-k]]==0)cnt--;
          if(mp[v[i-k]]==1)cnt++;
          mp[v[i]]++;
          if(mp[v[i]]==1)cnt++;
          if(mp[v[i]]==2)cnt--;
          total+=cnt;
    }
    cout<<total;
    return 0;
}
Tags: ,