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


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 long

using 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);
        }
    }
}