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 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);
}
}
}
0 Comments