Cod sursa(job #2571250)

Utilizator NicolaalexandraNicola Alexandra Mihaela Nicolaalexandra Data 4 martie 2020 21:55:00
Problema Distincte Scor 5
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.32 kb
#include <bits/stdc++.h>
#define DIM 100010
using namespace std;

ifstream fin ("distincte.in");
ofstream fout ("distincte.out");
int what_bucket[DIM],f[DIM],v[DIM];
long long sol[DIM];
int n,m,k,i,j,nr_buckets,lg,x,y;
struct query{
    int x,y,poz;
};
query qry[DIM];
vector <int> buckets[DIM];

inline int cmp (query a, query b){
    if (what_bucket[a.x] == what_bucket[a.y])
        return a.y < b.y;
    return what_bucket[a.x] < what_bucket[a.y];
}
int main (){

    fin>>n>>k>>m;
    for (i=1;i<=n;i++)
        fin>>v[i];
    lg = n / sqrt(n);

    if (n % lg == 0)
        nr_buckets = n / lg;
    else nr_buckets = n / lg + 1;

    for (i=1;i<=n;i++){
        if (i % lg == 0)
            what_bucket[i] = i / lg;
        else what_bucket[i] = i / lg + 1;
    }

    k = 0;
    for (i=1;i<=m;i++){
        fin>>x>>y;
        if (x > y)
            swap (x,y);

        if (y - x + 1 <= lg){
            long long sum = 0;
            for (j=x;j<=y;j++){
                f[v[j]]++;
                if (f[v[j]] == 1)
                    sum += v[j];
            }
            sol[i] = sum;

            for (j=x;j<=y;j++)
                f[v[j]] = 0;
        } else qry[++k] = {x,y,i};
    }

    sort (qry+1,qry+k+1,cmp);

    for (i=1;i<=k;i++)
        buckets[what_bucket[qry[i].x]].push_back(i);

    int pos = 0;
    for (i=1;i<=nr_buckets;i++){
        /// rezolv toate query urile din bucketul asta
        int st = (i-1) * lg, dr = min(n,i*lg);
        long long sum = 0;
        for (j=dr+1;j<=n;j++){

            f[v[j]]++;
            if (f[v[j]] == 1)
                sum += v[j];

            while (pos < buckets[i].size() && qry[buckets[i][pos]].y == j){

                long long sum_aux = sum;
                for (int t=qry[buckets[i][pos]].x;t<=dr;t++){
                    f[v[t]]++;
                    if (f[v[t]] == 1)
                        sum_aux += v[t];
                }

                sol[qry[buckets[i][pos]].poz] = sum_aux;

                /// acum demarchez
                for (int t=qry[buckets[i][pos]].x;t<=dr;t++)
                    f[v[t]]--;

                pos++;
            }
        }
        for (j=dr+1;j<=n;j++)
            f[v[j]] = 0;
    }

    for (i=1;i<=m;i++)
        fout<<sol[i]<<"\n";

    return 0;
}