Cod sursa(job #2191532)

Utilizator ibogdan25Ilie Ionut ibogdan25 Data 2 aprilie 2018 22:55:26
Problema Secventa 5 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.92 kb
// SortChar.cpp : Defines the entry point for the console application.
//

#include <queue>
#include <stdio.h>
#include <string>
#include <fstream>
#include <iostream>
#include <unistd.h>
#define PRIME 2531
using namespace std;

//ifstream f("secv5.in");
ofstream fout("secv5.out");
struct Hash{
    vector < pair<int,int> > numbers;
}H[PRIME];
int counter = 0;

int isInHash(int number) {
    int key = number % PRIME;
    for (int i = 0; i < H[key].numbers.size(); i++) {
        if (H[key].numbers[i].first == number) return 1;
    }
    return 0;
}
void addNumber(int number) {

    int key = number % PRIME;
    H[key].numbers.push_back(make_pair(number, 1));
    counter++;
}
void removeNumber(int number) {
    int key = number % PRIME;
    for (int i = 0; i < H[key].numbers.size(); i++) {
        if (H[key].numbers[i].first == number) {
            H[key].numbers.erase(H[key].numbers.begin() + i);
            break;
        }
    }
}
void update(int number, int numToAdd) {
    int key = number % PRIME;
    for (int i = 0; i < H[key].numbers.size(); i++) {
        if (H[key].numbers[i].first == number) {
            H[key].numbers[i].second += numToAdd;
            if (H[key].numbers[i].second == 0) {
                H[key].numbers.erase(H[key].numbers.begin() + i);
                counter--;
            }
            break;
        }
    }
}
int main() {
    deque <int> numbers;
    vector <int> elements;
    int n = 0, l = 0, g = 0, solution = 0, x = 0;
    FILE *rFile;
    rFile = fopen("secv5.in", "r");
    //f >> n >> l >> g;
    fscanf(rFile, "%d %d %d", &n, &l, &g);
    while (n--) {
        fscanf(rFile, "%d", &x);
        //f >> x;
        elements.push_back(x);
    }
    int i = 0, j = 0;
    while (i + l <= elements.size()) {
        x = elements[j];
        numbers.push_back(x);
        if (isInHash(x)) {
            update(x, 1);
        } else {
            addNumber(x);
        }
        if (counter >= l && counter <= g) {
            solution++;
        }
        if (counter > g) {
            int valoare = numbers.front();
            numbers.pop_front();
            update(valoare, -1);
            while (counter >= l){
                valoare = numbers.back();
                numbers.pop_back();
                update(valoare, -1);
                j--;
            }
            if (counter >= l && counter <= g) {
                solution++;
            }
            i++;
        }
        j++;

        if (j >= elements.size()) {
            int valoare = numbers.front();
            numbers.pop_front();
            update(valoare, -1);
            while (counter >= l || j >= elements.size()){
                valoare = numbers.back();
                numbers.pop_back();
                update(valoare, -1);
                j--;
            }
            i++;
        }
    }
    fout << solution;
    return 0;
}