Cod sursa(job #2715456)

Utilizator beingsebiPopa Sebastian beingsebi Data 3 martie 2021 18:23:11
Problema Distincte Scor 15
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.51 kb
#include <bits/stdc++.h>
#define int long long
using namespace std;
ifstream f("distincte.in");
ofstream g("distincte.out");
typedef vector<int>::iterator iter;
class idkbro
{
    idkbro *left, *right;
    int le, ri, ct;
    vector<int> arr;

public:
    void build(iter st, iter dr, int l, int r)
    {
        le = l;
        ri = r;
        if (st >= dr)
            return;
        if (l >= r)
        {
            ct = 1;
            return;
        }
        arr.reserve(dr - st + 1);
        arr.push_back(0);
        int mid = (l + r) / 2;
        auto fc = [mid](int x) {
            return x <= mid;
        };
        for (iter it = st; it != dr; it++)
            arr.push_back(arr.back() + fc(*it));
        iter pivot = stable_partition(st, dr, fc);
        left = new idkbro;
        right = new idkbro;
        left->build(st, pivot, l, mid);
        right->build(pivot, dr, mid + 1, r);
        ct = left->ct + right->ct;
    }
    int query(int x, int y)
    {
        if (x > y)
            return 0;
        if (le == ri)
            return le;
        int lb = arr[x - 1], rb = arr[y];
        return left->query(lb + 1, rb) + right->query(x - lb, y - rb);
    }
} idk;
int32_t main()
{
    int n, k, m;
    f >> n >> k >> m;
    vector<int> v(n + 1);
    for (int i = 1; i <= n; i++)
        f >> v[i];
    idk.build(v.begin(), v.end(), 1, k);
    for (int x, y; m; m--)
    {
        f >> x >> y;
        g << idk.query(x, y + 1) << '\n';
    }
    return 0;
}