# HackerEarth Greedy chairman problem solution

In this HackerEarth Greedy chairman problem solution One day, Madi, chairman of "Wal’s smart"company, decided to hire new employees.

His secretary, Dina J. Tramp, gave him a list of employees. At first glance, he thought that all candidates have a different experience, skills, etc. However, they were the same! The only thing that was unique to any candidate, is salary!(however, 2 or more employees can have the same value). After that, Madi decided to test his company’s programmer’s skill.

At first, he numbered all candidates from 1 to n. After that, he wrote down all salaries(Candidate with the number i wants salary ai). Then, he told him q questions. Every question had format l, r, and k. The question was, in how many ways he can choose exactly k candidates between l and r and hire them, such that Madi will spend a minimum amount of money (since the answer if very big, output it modulo (10^9+7)). His mighty programmist, Calif tried to solve this problem. Unfortunately, he was unsuccessful. And he asked for help from you.

## HackerEarth Greedy chairman problem solution.

`#include <bits/stdc++.h>#define pb push_back#define pp pop_back#define mp make_pair#define ld long double#define f first#define s second#define ll long longusing namespace std;const int N = 1e6 + 5;const int mod = 1e9 + 7;void add(int &a, int b){    a += b;    if (a >= mod) a -= mod;}int sum(int a, int b){       add(a, b);    return a;}int mult(int a, int b){    return (1ll * a * b) % mod;}int n, m, a[N], t[N], sz, f[N], inv[N];struct tree{    int l, r, s;}T[N * 40];void update(int u, int v, int p, int tl = 1, int tr = n){  T[v].s=T[u].s;  T[v].l=T[u].l;  T[v].r=T[u].r;    if (tl == tr){        T[v].s++;        return;    }    int tm = (tl + tr) / 2;    if (p <= tm){        T[v].l = ++sz;        update(T[u].l, T[v].l, p, tl, tm);    } else{        T[v].r = ++sz;        update(T[u].r, T[v].r, p, tm + 1, tr);    }    T[v].s = 0;    if (T[v].l) T[v].s += T[T[v].l].s;    if (T[v].r) T[v].s += T[T[v].r].s;}int bp(int a, int n){    int ans = 1;    while(n){        if (n & 1) ans = mult(ans, a);        a = mult(a, a);        n >>= 1;    }    return ans;}int cnk(int n, int k){    if (k > n || n < 0 || k < 0) return 0;    int ans = mult(f[n], inv[k]);    ans = mult(ans, inv[n - k]);    return ans;}int calc(int u,int v,int k,int f,int tl=1,int tr = n,int s=0){    if (tl == tr){        return cnk(T[v].s-T[u].s, f-s);         }    int tm=(tl+tr)/2;    int now = T[T[v].l].s-T[T[u].l].s;    if (now>=k) return calc(T[u].l,T[v].l,k,f,tl,tm,s);    else return calc(T[u].r,T[v].r,k - now,f,tm+1,tr,s+now);}int main(){//  ios_base::sync_with_stdio(0);    clock_t start = clock();    scanf("%d%d\n", &n, &m);    f[0] = inv[0] = 1;    for (int i = 1;i <= n;i++){        f[i] = mult(f[i - 1], i);    }    inv[n]=bp(f[n],mod-2);    for(int i=n-1;i>=0;i--){        inv[i]=mult(inv[i+1],i+1);    }     vector < int > all;    for (int i = 1;i <= n;i++){        scanf("%d", &a[i]);        all.pb(a[i]);    }    sort(all.begin(), all.end());    all.resize(unique(all.begin(), all.end()) - all.begin());    for (int i = 1;i <= n;i++){        a[i] = lower_bound(all.begin(), all.end(), a[i]) -all.begin()+ 1;    update(t[i - 1], t[i] = ++sz, a[i]);  }    while(m--)    {        int l, r, k, ans;        scanf("%d%d%d\n", &l, &r, &k);        printf("%d\n", calc(t[l-1],t[r],k,k));              }    return 0;}`

### Second solution

`import java.io.*;import java.util.*;public class AugClashGreedyChairman {    static ArrayList<Node> nodes;    static int root[];    static long fact[], inv[];    static final int mod = (int) 1e9 + 7;    static final int MAXN = (int) 2e5;    static final int MAXV = (int) 1e7;    public static void main(String[] args) {        InputReader in = new InputReader(System.in);        PrintWriter out = new PrintWriter(System.out);        preprocess();        int n = in.nextInt();        int m = in.nextInt();        check(1, n, MAXN);        check(1, m, MAXN);        int a[] = new int[n + 1];        for (int i = 1; i <= n; i++) {            a[i] = in.nextInt();            check(1, a[i], MAXV);        }        root = new int[n + 1];        root[0] = 0;        nodes = new ArrayList<Node>();        nodes.add(new Node());        for (int i = 1; i <= n; i++)            root[i] = update(root[i - 1], 1, MAXV, a[i]);        while (m-- > 0) {            int l = in.nextInt();            int r = in.nextInt();            int k = in.nextInt();            check(1, l, n);            check(1, r, n);            check(l, r, n);            check(Integer.MIN_VALUE, k, r - l + 1);            out.println(find(1, MAXV, root[l - 1], root[r], k));        }        out.close();    }    static long find(int start, int end, int leftRoot, int rightRoot, int k) {        if (start == end)            return C(sum(rightRoot) - sum(leftRoot), k);        int mid = (start + end) >> 1;        int leftSum = sum(left(rightRoot)) - sum(left(leftRoot)); //number of nodes in [start,mid]        if (leftSum >= k)            return find(start, mid, left(leftRoot), left(rightRoot), k);        else            return find(mid + 1, end, right(leftRoot), right(rightRoot), k - leftSum);    }    static int update(int prevRoot, int start, int end, int x) {        Node now = new Node();        now.sum = sum(prevRoot);        now.left = left(prevRoot);        now.right = right(prevRoot);        nodes.add(now);        int idx = nodes.size() - 1;        if (start == end) {            now.sum++;            return idx;        }        int mid = (start + end) >> 1;        if (x <= mid) {            int leftSon = left(prevRoot);            now.left = update(leftSon, start, mid, x);        }        else {            int rightSon = right(prevRoot);            now.right = update(rightSon, mid + 1, end, x);        }        now.sum = sum(now.left) + sum(now.right);        return idx;    }    static long C(int n, int r) {        if (r < 0 || r > n)            return 0;        long ans = fact[n];        ans *= inv[r];        ans %= mod;        ans *= inv[n - r];        ans %= mod;        return ans;    }    static class Node {        int sum, left, right;        Node() {            sum = 0;            left = -1;            right = -1;        }    }    static int sum(int idx) {        return idx == -1 ? 0 : nodes.get(idx).sum;    }    static int left(int idx) {        return idx == -1 ? -1 : nodes.get(idx).left;    }    static int right(int idx) {        return idx == -1 ? -1 : nodes.get(idx).right;    }    static void preprocess() {        int N = 2 * MAXN + 100;        fact = new long[N];        fact[0] = 1;        for (int i = 1; i < N; i++)            fact[i] = (fact[i - 1] * i) % mod;        inv = new long[N];        inv[N - 1] = pow(fact[N - 1], mod - 2, mod);        for (int i = N - 2; i >= 0; i--)            inv[i] = ((i + 1) * inv[i + 1]) % mod;    }    static long pow(long a, int b, int mod) {        if (b == 0)            return 1;        long t = pow(a, b >> 1, mod);        t = (t * t) % mod;        if ((b & 1) != 0)            t = (t * a) % mod;        return t;    }    static void check(int start, int key, int end) {        if (key < start || key > end)            throw new RuntimeException();    }    static class InputReader {        private final InputStream stream;        private final byte[] buf = new byte[8192];        private int curChar, snumChars;        private SpaceCharFilter filter;        public InputReader(InputStream stream) {            this.stream = stream;        }        public int snext() {            if (snumChars == -1)                throw new InputMismatchException();            if (curChar >= snumChars) {                curChar = 0;                try {                    snumChars = stream.read(buf);                } catch (IOException e) {                    throw new InputMismatchException();                }                if (snumChars <= 0)                    return -1;            }            return buf[curChar++];        }        public int nextInt() {            int c = snext();            while (isSpaceChar(c)) {                c = snext();            }            int sgn = 1;            if (c == '-') {                sgn = -1;                c = snext();            }            int res = 0;            do {                if (c < '0' || c > '9')                    throw new InputMismatchException();                res *= 10;                res += c - '0';                c = snext();            } while (!isSpaceChar(c));            return res * sgn;        }        public boolean isSpaceChar(int c) {            if (filter != null)                return filter.isSpaceChar(c);            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;        }        public interface SpaceCharFilter {            public boolean isSpaceChar(int ch);        }    }}`