Cod sursa(job #2694674)

Utilizator cristi_macoveiMacovei Cristian cristi_macovei Data 10 ianuarie 2021 13:34:07
Problema Secventa 5 Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <iostream>
#include <fstream>
#include <unordered_map>

const int NMAX = (1 << 20);

int64_t n, qLeft, qRight;

int64_t a[1 + NMAX];

std::unordered_map<int64_t, int64_t> hashmap;

void read() {
  std::ifstream in("secv5.in");

  in >> n >> qLeft >> qRight;

  for (int64_t i = 1; i <= n; ++i)
    in >> a[i];
}

int64_t countSeq(int64_t target) {
  if (target == 0)
    return 0;

  hashmap.clear();

  int64_t left = 1, cnt = 1;
  int64_t ans = 0;
  hashmap[a[1]] = 1;
  for (int64_t i = 2; i <= n; ++i) {
    if (hashmap[a[i]] == 0) {
      if (cnt < target) {
        ++cnt;
        hashmap[a[i]] = 1;
      } else {
        while (hashmap[a[left]] != 1) {
          --hashmap[a[left]];
          ans += i - left;
          ++left;
        }
        --hashmap[a[left]];
        ans += i - left;
        ++left;
        hashmap[a[i]] = 1;
      }
    } else {
      ++hashmap[a[i]];
    }
  }

  while (left <= n) {
    ans += n - left + 1;
    ++left;
  }

  return ans;
}

int main() {
  read();

  int64_t left = countSeq(qLeft - 1);
  int64_t right = countSeq(qRight);

  std::ofstream out("secv5.out");
  out << right - left << '\n';

  return 0;
}