Cod sursă (job #799572)

#include <fstream>
#include <algorithm>

using namespace std;

ifstream fin("calin.in");
ofstream fout("calin.out");

const int Nmax = 200005;

struct subiect{
    int tip;
    int poz_finish, lungime;
};

struct query{
    int capat_st, capat_dr;
    int valoare, indice;
};

int n, q;
int indici[Nmax];
int aib[Nmax], sol[Nmax];
subiect subiecte[Nmax];
query queries[Nmax];

int lsb(int x){
    return (x & (-x));
}

void aib_update(int poz, int val){
    for(int i = poz; i <= n; i += lsb(i)){
        aib[i] += val;
    }
}

int aib_query_poz(int poz){
    int sol = 0;

    for(int i = poz; i >= 1; i -= lsb(i)){
        sol += aib[i];
    }

    return sol;
}

int aib_query(int capat_st, int capat_dr){
    return aib_query_poz(capat_dr) - aib_query_poz(capat_st - 1);
}

void citire_sir(){
    int cate, tip;

    fin >> n >> q;
    cate = 0;

    for(int i = 1; i <= n; i++){
        fin >> tip;

        if(tip == subiecte[cate].tip){
            subiecte[cate].lungime++;
        }
        else{
            subiecte[cate].poz_finish = i - 1;

            cate++;
            subiecte[cate].tip = tip;
            subiecte[cate].lungime = 1;
        }
    }
    subiecte[cate].poz_finish = n;
    n = cate;

    for(int i = 1; i <= n; i++){
        indici[i] = i;
    }
}

void citire_queries(){
    for(int i = 1; i <= q; i++){
        fin >> queries[i].capat_st >> queries[i].capat_dr >> queries[i].valoare;
        queries[i].indice = i;
    }
}

bool cmp_valoare(query a, query b){
    return a.valoare > b.valoare;
}

bool cmp_lungme(int a, int b){
    return subiecte[a].lungime > subiecte[b].lungime;
}

void sortari(){
    sort(indici + 1, indici + n + 1, cmp_lungme);
    sort(queries + 1, queries + q + 1, cmp_valoare);
}

int caut_bin(int val){
    int lft, rgt, mid, sol;

    lft = 1;
    rgt = n;
    sol = 1;
    while(lft <= rgt){
        mid = (lft + rgt) / 2;

        if(val <= subiecte[mid].poz_finish){
            sol = mid;
            rgt = mid - 1;
        }
        else{
            lft = mid + 1;
        }
    }
    return sol;
}

void calculare_solutie(){
    int p1, p2;
    int solutie, inceput, sfarsit;

    p1 = 1;
    for(p2 = 1; p2 <= q; p2++){
        while(p1 <= n && subiecte[indici[p1]].lungime >= queries[p2].valoare){
            aib_update(indici[p1], 1);
            p1++;
        }

        solutie = 0;
        inceput = caut_bin(queries[p2].capat_st);
        sfarsit = caut_bin(queries[p2].capat_dr);

        if(inceput == sfarsit){
            if(queries[p2].capat_dr - queries[p2].capat_st + 1 >= queries[p2].valoare){
                solutie++;
            }
        }
        else{
            if(sfarsit - inceput >= 2){
                solutie += aib_query(inceput + 1, sfarsit - 1);
            }

            if(subiecte[inceput].poz_finish - queries[p2].capat_st + 1 >= queries[p2].valoare){
                solutie++;
            }
            if(queries[p2].capat_dr - subiecte[sfarsit - 1].poz_finish >= queries[p2].valoare){
                solutie++;
            }
        }

        sol[queries[p2].indice] = solutie;
    }
}

void afisare_raspunsuri_queries(){
    for(int i = 1; i <= q; i++){
        fout << sol[i] << '\n';
    }
}

int main(){
    citire_sir();
    citire_queries();

    sortari();
    calculare_solutie();

    afisare_raspunsuri_queries();

    return 0;
}