Cod sursa(job #2906482)

Utilizator Balauta_AlbertBalauta Albert Balauta_Albert Data 26 mai 2022 10:50:35
Problema Secventa 5 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <iostream>
#include <bits/stdc++.h>
#include <fstream>
#include <map>

using namespace std;
ifstream in("secv5.in");
ofstream out("secv5.out");
const static long mod = 66013;
vector<vector<unsigned int>> v;
unsigned int dim=0;
unsigned int search(unsigned int value) {
    unsigned int key = value % mod;
    for (unsigned int i = 0; i < v[key].size(); ++i)
        if (v[key][i] == value)
            return i;
    return -1;
}

void insert(unsigned int value) {
    if(search(value) == -1) dim++;
    v[value % mod].push_back(value);
}

void erase(unsigned int value) {
    unsigned int key = value % mod;
    unsigned int s = v[key].size() - 1;
    unsigned int ind = search(value);
    if (ind != -1) {
        v[key][ind] = v[key][s];
        v[key].pop_back();
    }
    if(search(value) == -1) dim--;
}



int main() {
    v.resize(mod);
    vector<unsigned int> v1;
    unsigned int l, u, n;
    unsigned int x;
    in >> n;
    in >> l >> u;
    for (unsigned int i = 0; i < n; i++) {
        in >> x;
        v1.push_back(x);
    }
    long long s = 0, cntU = 0, cntL = 0;

    for (unsigned int i = 0; i < n; i++) {
        insert(v1[i]);
        while (dim > u) {
            erase(v1[s++]);
        }

        cntU += (i - s + 1);
    }
    s = 0;

    v.clear();
    v.resize(mod);
    dim = 0 ;
    for (unsigned int i = 0; i < n; i++) {
        insert(v1[i]);
        while (dim >= l)
            erase(v1[s++]);
        cntL += (i - s + 1);
    }
    out<<cntU - cntL;
    return 0;
}