# HackerRank Starfleet problem solution

In this HackerRank Starfleet problem solution, we have given the initial positions of the space-fighters, and their velocity, you are to answer queries of the following form:

YU YD T

where YU, YD is the bounds on the y-axis inside which YODA can block a frequency at time T. In the region described by the query, after a time of T seconds from the start, if Yoda can choose one frequency (F) he wishes to, what is the maximum number of communications he can block?

## Problem solution in Python programming.

```import bisect
from collections import defaultdict

N,Q,_ = map(int,input().split())
a = defaultdict(list)
y = list()
for _ in range( N ):
_,y_,freq = map(int,input().split())
a[ freq ].append( y_ )
y.append( y_ )

a = { freq:sorted(y) for freq,y in a.items() if len(y) > 1 }
y = sorted( y )

res = []
for _ in range( Q ):
y_max, y_min, T = map(int,input().split())
lres = 0
index_start = bisect.bisect_left(y, y_min)
if y[ index_start ] <= y_max:
lres = 1
for freq in a:
index_start = bisect.bisect_left( a[freq], y_min )
index_stop = bisect.bisect_right( a[freq], y_max )
lres = max( lres, index_stop - index_start )
res.append( lres )
print(*res, sep = '\n')```

## Problem solution in Java Programming.

```import java.io.*;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.*;
import java.util.stream.Collectors;

// Library Query
public class Solution
{
static class DEBUG {
static public final boolean ON = false;

static public void ASSERT( boolean ok, String msg ) {
if (!ok)
throw new RuntimeException(msg);
}
}

static class Scanner {
private final String data;
private int curPos;
private int len;
private boolean hasData = true;

Scanner(String dt) {
data = dt;
len = data.length();
}

int getNextInt() {

while (data.charAt(curPos) <= 32)
curPos++;

int res = 0;
int k = 1;

if (data.charAt(curPos)=='-') {
curPos++;
k = -1;
}

try {
while (data.charAt(curPos) > 32) {
res *= 10;
res += data.charAt(curPos) - '0';
curPos++;
}
} catch (Exception ign) {
int r = 0;
}

return res * k;
}

void nextLine() {
while (data.charAt(curPos) < 32)
curPos++;
while (data.charAt(curPos) >= 32) {
curPos++;
}
while (data.charAt(curPos) < 32)
curPos++;
}

boolean atNewLine() {
return data.charAt(curPos) < 32;
}

boolean hasNextLine() {
return curPos + 3 < len;
}
}

static class Fighter {
final int y;
final int f;

Fighter(int y, int f) {
this.y = y;
this.f = f;
}
}

static class FighterFreq {
final int f;
final int n; // number of fighters

FighterFreq(int f, int n) {
this.f = f;
this.n = n;
}
}

static class FighterFreqBucket {

int ly;
int ry; // not included

// sorted dec by n
final Map< Integer, FighterFreq >  fighterFreqIndex; // key: Freq
final List< FighterFreq > fighterFreqRatings;
Map< Integer, List<Fighter> > sourceData; // need for leaves

private FighterFreqBucket L;
private FighterFreqBucket R;

// R is not included
// data expetced to be filtered for this Node, Key:  Frequency
FighterFreqBucket(int ly, int ry, Map< Integer, List<Fighter> > data, FighterFreqBucket parent ) {
this.ly = ly;
this.ry = ry;

// Build own data
fighterFreqIndex = new HashMap<>();
fighterFreqRatings = data.entrySet().stream().map(ent -> new FighterFreq( ent.getKey(), ent.getValue().size() )  ).collect( Collectors.toList() );

int sumn = 0;
for (FighterFreq ff : fighterFreqRatings ) {
fighterFreqIndex.put( ff.f, ff );
sumn += ff.n;
}

// sorting by numbers. First - biggest number
fighterFreqRatings.sort( (ff1, ff2) -> {
if (ff1.n == ff2.n)
return parent==null ? 0 : -Integer.compare( parent.getN( ff1.f ), parent.getN( ff2.f ) );
else
return -Integer.compare( ff1.n, ff2.n );
} );

if ( sumn > 15 && ry-ly > 1 ) {
// has children (until one freq will be reached)...

Map< Integer, List<Fighter> > LData = new HashMap<>();
Map< Integer, List<Fighter> > RData = new HashMap<>();
int cy = (ry+ly)/2;

for ( Map.Entry< Integer, List<Fighter> > ent : data.entrySet() ) {
int f = ent.getKey();
ArrayList<Fighter> LFs = new ArrayList<>();
ArrayList<Fighter> RFs = new ArrayList<>();

ent.getValue().forEach( fg -> {
if (fg.y < cy)
else
} );

if (!LFs.isEmpty())
LData.put(f,LFs);
if (!RFs.isEmpty())
RData.put(f,RFs);
}
L = new FighterFreqBucket(ly, cy, LData, this);
R = new FighterFreqBucket(cy, ry, RData, this);
sourceData = null;
}
else {
L=R=null;
sourceData = data;
}
}

int getN(int f) {
FighterFreq ff = fighterFreqIndex.get(f);
if (ff==null)
return 0;
return ff.n;
}

void collectAllBuckets( int y1, int y2, List<FighterFreqBucket> result ) {
if ( ly == y1 && ry==y2 ) {
return;
}

if (L==null) {
// No kids, and range doesn't match.
// Creating a new one from the data

Map< Integer, List<Fighter> > yyData = new HashMap<>();
for ( Map.Entry< Integer, List<Fighter> > ent : sourceData.entrySet() ) {
int f = ent.getKey();
List<Fighter> ff = ent.getValue().stream().filter( fighter -> fighter.y>=y1 && fighter.y<y2 ).collect(Collectors.toList());
if (!ff.isEmpty())
yyData.put( f,ff );
}
result.add( new FighterFreqBucket(y1, y2, yyData, this) );
return;
}

// Need delgate to the children
int cy = (ly + ry)/2;

if ( y1<cy )
L.collectAllBuckets( y1, Math.min(cy,y2), result );
if ( y2>cy ) {
R.collectAllBuckets(Math.max(cy, y1), y2, result);
}
}

int getDataSize() {return fighterFreqRatings.size();}

FighterFreq getFF(int idx) { return idx>=fighterFreqRatings.size() ? null : fighterFreqRatings.get(idx); }

int calcGain(int idx) {
int sz = fighterFreqRatings.size();
if ( idx>=sz )
return 0;

return fighterFreqRatings.get(idx).n - fighterFreqRatings.get(Math.min( sz-1,idx+5)).n;
}
}

static class BucketInfo {
final int idx; // bucket index
int       nmax = 0;
int       dataIdx = 0;
int       gain = 0;

BucketInfo(int idx, int nmax, int gain) {
this.idx = idx;
this.nmax = nmax;
this.gain = gain;
}
}

public static int calcMaxN( List<FighterFreqBucket> buckets ) {
HashSet<Integer> precessedFreqs = new HashSet<>();
int maxFreqs = buckets.stream().map( b-> b.getDataSize() ).max(Integer::compare).get();
int maxN = 0;

/*        int theorMax = 0;

ArrayList<BucketInfo> weights = new ArrayList<>();
for (int t=0; t<buckets.size();t++) {

FighterFreqBucket b = buckets.get(t);

FighterFreq ff = b.getFF(0);

int n = ff==null? 0 : ff.n;
theorMax += n;

weights.add( new BucketInfo(t, n, b.calcGain(0) ) );
}

//        if (DEBUG.ON) {
//          int totalItems = buckets.stream().mapToInt(b -> b.fighterFreqIndex.size()).sum();
//        System.out.println("Total items = " + totalItems);
//  }

weights.sort( (o1, o2) -> -Integer.compare(o1.gain, o2.gain) );

int iterations = 0;
int maxIter = 0;

while (maxN < theorMax ) {
// Processing Max Fs first

iterations++;

BucketInfo bi = weights.get(0);
FighterFreqBucket b = buckets.get(bi.idx);
FighterFreq ff = b.getFF(bi.dataIdx++);

if (ff==null) {
theorMax -= bi.nmax;
bi.nmax = 0;
bi.gain = -1;
}
else {
if (! precessedFreqs.contains(ff.f)) {

int ffN = buckets.stream().mapToInt(bucket -> bucket.getN(ff.f)).sum();

if (maxN < ffN) {
maxN = ffN;
maxIter = iterations;
}
}

theorMax -= bi.nmax - ff.n;
bi.nmax = ff.n;
bi.gain = b.calcGain(bi.dataIdx);
}

if (weights.size()>1) {
for (int t=1;t<weights.size();t++) {
if ( weights.get(t-1).gain < weights.get(t).gain ) {
BucketInfo sw = weights.get(t-1);
weights.set(t-1, weights.get(t) );
weights.set(t, sw );
}
else {
break;
}

}
}

}

if (DEBUG.ON) {
if (maxIter>90) {
int totalItems = buckets.stream().mapToInt(b -> b.fighterFreqIndex.size()).sum();
System.out.println("totalItems=" + totalItems + "  Iterations= " + iterations + " maxIter=" + maxIter);
}
}*/

int iterations = 0;
int maxIter = 0;

for ( int i=0; i<maxFreqs && iterations<200; i++ ) {
int theorMax = 0;

for (int r=buckets.size()-1; r>=0; r--  ) {
iterations++;

FighterFreqBucket b = buckets.get(r);

FighterFreq ff = b.getFF(i);
if (ff==null) {
buckets.remove(r);
continue;
}

theorMax += ff.n;

if (precessedFreqs.contains(ff.f)) {
continue;
}

int ffN = 0;

for ( FighterFreqBucket bb : buckets )
ffN += bb.getN(ff.f);

//buckets.stream().mapToInt( bucket -> bucket.getN(ff.f) ).sum();

if (maxN < ffN) {
maxN = ffN;
maxIter = iterations;
}
}

if (maxN>=theorMax) // all tops are found
break;
}

if (DEBUG.ON) {
if (maxIter>200)
System.out.println("iterations=" + iterations+ " maxIter="+maxIter + " maxFreqs="+maxFreqs);
}

return maxN;
}

public static void main(String[] args) {
Scanner input = null;
ArrayList<Integer> results = null;

try {
ByteArrayOutputStream result = new ByteArrayOutputStream();
byte[] buffer = new byte[10240];
int length;
while ((length = System.in.read(buffer)) != -1) {
result.write(buffer, 0, length);
}
input = new Scanner( result.toString("UTF-8") );

} catch (Exception ex) {
ex.printStackTrace();
return;
}

long startT = System.currentTimeMillis();

int N = input.getNextInt(); // number of space fighters
int Q = input.getNextInt();
input.getNextInt(); // Velocity - we don't care

ArrayList<Fighter> fighters = new ArrayList<>();

int minY = 0;
int maxY = 0;

for (int n=0; n<N; n++) {
input.getNextInt(); // x - don't care
int y = input.getNextInt();
int f = input.getNextInt();

if (minY > y) minY = y;
if (maxY < y) maxY = y;
}

TreeSet<Integer>  singleFFs = new TreeSet<>();

// Let's build the index from the ships
Map< Integer, List<Fighter> > data = fighters.stream().collect( Collectors.groupingBy( f -> f.f, Collectors.toList() )).
entrySet().stream().filter( ent -> {
if (ent.getValue().size()==1) {
return false;
}
return true;
} ).collect( Collectors.toMap(o -> o.getKey(), o->o.getValue()) );

FighterFreqBucket rootBucket = new FighterFreqBucket(minY, maxY+1, data, null );
ArrayList<Integer> res = new ArrayList<>();

long buildT = System.currentTimeMillis();

long buildBucketsT = 0;
long calcTime = 0;

// Processign Queries
for (int q=0;q<Q;q++) {

long t1 = System.currentTimeMillis();

int y2 = input.getNextInt();
int y1 = input.getNextInt();
input.getNextInt(); // T - don't care

y1 = Math.max(y1, minY);
y2 = Math.min(y2, maxY);

// Calculatign the result
List < FighterFreqBucket > buckets = new ArrayList<>();
rootBucket.collectAllBuckets(y1,y2+1, buckets );

long t2 = System.currentTimeMillis();

int ffn = calcMaxN( buckets);

if (ffn==0) {
// Might be one of singles...
Integer lo = singleFFs.ceiling( y1 );
Integer hi = singleFFs.floor(y2);

if (lo!=null && hi!=null && lo<=hi)
ffn = 1;
}

if (results!=null) {
if (results.get(res.size()).intValue() != ffn)
throw new RuntimeException("Res wrong failure");
}

long t3 = System.currentTimeMillis();

buildBucketsT+= t2-t1;
calcTime += t3-t2;

}

long finishT = System.currentTimeMillis();

System.out.println("totalT="+(finishT-startT) + " buildT="+ (buildT-startT) + " procT="+ (finishT-buildT) + "  buildBucketsT="+buildBucketsT+ " calcTime="+calcTime);

try {
FileWriter fw = new FileWriter(System.getenv("OUTPUT_PATH"));
StringBuilder sb = new StringBuilder();
res.forEach(i -> sb.append(i).append("\n"));

fw.write(sb.toString());
fw.close();
}
catch (Exception ex) {
ex.printStackTrace();
}
}
}```

## Problem solution in C++ programming.

```#include <algorithm>
#include <iostream>
#include <cstring>
#include <cassert>
#include <iomanip>
#include <cstdio>
#include <vector>
#include <string>
#include <stack>
#include <cmath>
#include <ctime>
#include <queue>
#include <list>
#include <map>
#include <set>

#define For(i,a,b) for(register int (i)=(a);(i)<=(b);(i)++)
#define FOR(i,a) For(i,1,a)
#define Ford(i,a,b) for(register int (i)=(a);(i)>=(b);(i)--)
#define Rep(i,a,b) for(register int (i)=(a);(i)<(b);(i)++)
#define REP(i,a) Rep(i,0,a)
#define type(x) __typeof(x.begin())
#define foreach(it,x) for(__typeof(x.begin()) it = x.begin() ; it!=x.end() ; it++ )

#define NEW(x,n) (x*)calloc(n,sizeof(x))
#define fill(x,y) memset(x,y,sizeof x)
#define all(x) x.begin(),x.end()
#define compress(x) {sort(all(x));(x).resize(unique(all(x))-(x).begin());}
#define two(x) (1LL<<(x))
#define fi first
#define se second
#define gcd __gcd
#define pb push_back
#define mp make_pair

#ifdef KAZAR
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define dbg(x) cerr<<#x<<":"<<(x)<<endl
#define dg(x) cerr<<#x<<":"<<(x)<<' '
#else
#define eprintf(...) 0
#define dbg(x) 0
#define dg(x) 0
#endif

using namespace std;

typedef long long Lint;
typedef long double ld;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;

const int inf = 1e9+5143;
const Lint Linf = 1e18+5413;
const double eps = 1e-15;
const double pi = acos(-1);

template<class T> inline void umax(T &a,T b){if(a<b) a = b ; }
template<class T> inline void umin(T &a,T b){if(a>b) a = b ; }
template<class T> inline T abs(T a){return a>0 ? a : -a;}
template<class T> inline T lcm(T a,T b){
return a/gcd(a,b)*b;
}

int res = 0LL ;int neg ;
while(1){
char ch = getchar();
if(ch>='0' && ch<='9' || ch=='-'){
if(ch=='-') neg = -1;
else neg = 1 , res = ch-'0';
break;
}
}
while(1){
char ch = getchar();
if(ch>='0' && ch<='9') res*=10 , res+=ch-'0';
else break;
}
return res*neg;
}

const int N = 492717;
const int SQ = 300;

ii a[N];
int f[N];
vi valsx , vals;
vi occurance[N];
vi huges;
int ans[N];
int q;
vi here[N];

void get_damn_input(){

FOR(i,n){
valsx.pb(a[i].fi);
}

compress(valsx);

FOR(i,n){
a[i].fi = lower_bound(all(valsx),a[i].fi) - valsx.begin() + 1;
}

sort(a + 1,a + 1 + n);

FOR(i,n){
vals.pb(a[i].se);
}

compress(vals);

FOR(i,n){
f[i] = lower_bound(all(vals),a[i].se) - vals.begin() + 1;
assert(f[i] < N);
occurance[f[i]].pb(a[i].fi);
assert(a[i].fi < N);
here[a[i].fi].pb(f[i]);
}

REP(i,N) compress(here[i]);

REP(i,vals.size() + 5){
sort(all(occurance[i]));
if(occurance[i].size() > SQ){
huges.pb(i);
}
}

FOR(i,q){
int r = upper_bound(all(valsx),read()) - valsx.begin();
int l = lower_bound(all(valsx),read()) - valsx.begin() + 1;
eprintf("query %d , %d\n",l,r);
assert(r < N);
}

}

int kd[N * 10];

void put(int k,int b,int e,int x,int val){
assert(k < N * 10);
if(b > x || e < x) return;
if(b == e){
assert(val > 0);
umax(kd[k],val);
return;
}
put(k + k,b,(b+e)/2,x,val);
put(k + k + 1,(b+e)/2 + 1,e,x,val);
kd[k] = max(kd[k + k],kd[k + k + 1]);
}

int get(int k,int b,int e,int x1,int x2){
assert(k < N * 10);
if(b > x2 || e < x1) return 0;
if(b >= x1 && e <= x2) return kd[k];
return max(get(k + k,b,(b+e)/2,x1,x2),get(k + k + 1,(b+e)/2+1,e,x1,x2));
}

void insert(int idx,int where){
assert(idx < N);
if(occurance[idx].size() > SQ) return;
int cur = 0;
Ford(i,occurance[idx].size() - 1,0){
if(occurance[idx][i] <= where){
put(1,1,N,occurance[idx][i],++cur);
}
}
}

int main(){

#ifdef KAZAR
freopen("f.input","r",stdin);
freopen("f.output","w",stdout);
freopen("error","w",stderr);
#endif

get_damn_input();

REP(i,10){
eprintf("here %d: ",i);
foreach(it,here[i]) eprintf("%d ",*it);
eprintf("\n");
}

dbg(huges.size());

REP(i,N){
assert(i < N);
foreach(it,here[i]){
insert(*it,i);
eprintf("inserting i:%d f:%d then : %d\n",i,*it,get(1,1,N,1,i));
}
int r = i;
int l = it->fi;
assert(l < N);
assert(r < N);
int res = get(1,1,N,l,r);
foreach(huge,huges){
assert(*huge < N);
umax(res,int(upper_bound(all(occurance[*huge]),r) - lower_bound(all(occurance[*huge]),l)) );
}
ans[it->se] = res;
}
}

FOR(i,q) printf("%d\n",ans[i]);

return 0;
}```

## Problem solution in C programming.

```#include <stdio.h>
#include <stdlib.h>
#include <math.h>
typedef struct{
int u;
int w;
} node;
void QQ(int x,int y);
void removee(int x);
void sort_a2(int*a,int*b,int size);
void merge2(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int left_size,int right_size);
void sort_a3(int*a,int*b,int*c,int size);
void merge3(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int*c,int*left_c,int*right_c,int left_size,int right_size);
void update( int i, int val );
int get_i(int*a,int num,int size);
int med(int*a,int size);
void heap_insert(node *heap,node *elem,int *size,int *heap_list);
void heap_update(node *heap,node *elem,int *heap_list,int size);
int a[50000],b[50000]={0},q[30000],q1[30000],q2[30000],y[50000],f[50000],idx[50000],ans[30000],heap_list[50000]={0},cl,cr,heap_size=0;
node heap[50001];

int main(){
int NN,Q,V,x,i;
scanf("%d%d%d",&NN,&Q,&V);
for(i=0;i<NN;i++){
scanf("%d%d%d",&x,y+i,f+i);
idx[i]=i;
}
for(i=0;i<Q;i++)
scanf("%d%d%d",q2+i,q1+i,&x);
sort_a2(y,f,NN);
for(i=0;i<Q;i++){
q1[i]=get_i(y,q1[i],NN);
q2[i]=get_i(y,q2[i]+1,NN);
}
sort_a2(f,idx,NN);
for(i=x=0;i<NN;i++){
if(i && f[i]!=f[i-1])
x++;
a[idx[i]]=x;
}
for(i=0,x=(int)sqrt(NN);i<Q;i++){
q[i]=q1[i]/x;
y[i]=q2[i];
idx[i]=i;
}
sort_a3(q,y,idx,Q);
for(i=cl=cr=0;i<Q;i++){
QQ(q1[idx[i]],q2[idx[i]]);
ans[idx[i]]=heap[1].w;
}
for(i=0;i<Q;i++)
printf("%d\n",ans[i]);
return 0;
}
void QQ(int x,int y){
while(cl<x)
removee(cl++);
while(cl>x)
while(cr<y)
while(cr>y)
removee(--cr);
return;
}
b[a[x]]++;
update(a[x],b[a[x]]);
return;
}
void removee(int x){
b[a[x]]--;
update(a[x],b[a[x]]);
return;
}
void sort_a2(int*a,int*b,int size){
if (size < 2)
return;
int m = (size+1)/2,i;
int*left_a,*left_b,*right_a,*right_b;
left_a=(int*)malloc(m*sizeof(int));
right_a=(int*)malloc((size-m)*sizeof(int));
left_b=(int*)malloc(m*sizeof(int));
right_b=(int*)malloc((size-m)*sizeof(int));
for(i=0;i<m;i++){
left_a[i]=a[i];
left_b[i]=b[i];
}
for(i=0;i<size-m;i++){
right_a[i]=a[i+m];
right_b[i]=b[i+m];
}
sort_a2(left_a,left_b,m);
sort_a2(right_a,right_b,size-m);
merge2(a,left_a,right_a,b,left_b,right_b,m,size-m);
free(left_a);
free(right_a);
free(left_b);
free(right_b);
return;
}
void merge2(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int left_size,int right_size){
int i = 0, j = 0;
while (i < left_size|| j < right_size) {
if (i == left_size) {
a[i+j] = right_a[j];
b[i+j] = right_b[j];
j++;
} else if (j == right_size) {
a[i+j] = left_a[i];
b[i+j] = left_b[i];
i++;
} else if (left_a[i] <= right_a[j]) {
a[i+j] = left_a[i];
b[i+j] = left_b[i];
i++;
} else {
a[i+j] = right_a[j];
b[i+j] = right_b[j];
j++;
}
}
return;
}
void sort_a3(int*a,int*b,int*c,int size){
if (size < 2)
return;
int m = (size+1)/2,i;
int *left_a,*left_b,*left_c,*right_a,*right_b,*right_c;
left_a=(int*)malloc(m*sizeof(int));
right_a=(int*)malloc((size-m)*sizeof(int));
left_b=(int*)malloc(m*sizeof(int));
right_b=(int*)malloc((size-m)*sizeof(int));
left_c=(int*)malloc(m*sizeof(int));
right_c=(int*)malloc((size-m)*sizeof(int));
for(i=0;i<m;i++){
left_a[i]=a[i];
left_b[i]=b[i];
left_c[i]=c[i];
}
for(i=0;i<size-m;i++){
right_a[i]=a[i+m];
right_b[i]=b[i+m];
right_c[i]=c[i+m];
}
sort_a3(left_a,left_b,left_c,m);
sort_a3(right_a,right_b,right_c,size-m);
merge3(a,left_a,right_a,b,left_b,right_b,c,left_c,right_c,m,size-m);
free(left_a);
free(right_a);
free(left_b);
free(right_b);
free(left_c);
free(right_c);
return;
}
void merge3(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int*c,int*left_c,int*right_c,int left_size,int right_size){
int i = 0, j = 0;
while (i < left_size|| j < right_size) {
if (i == left_size) {
a[i+j] = right_a[j];
b[i+j] = right_b[j];
c[i+j] = right_c[j];
j++;
} else if (j == right_size) {
a[i+j] = left_a[i];
b[i+j] = left_b[i];
c[i+j] = left_c[i];
i++;
} else if (left_a[i] == right_a[j]) {
if(left_b[i]<=right_b[j]){
a[i+j] = left_a[i];
b[i+j] = left_b[i];
c[i+j] = left_c[i];
i++;
}
else{
a[i+j] = right_a[j];
b[i+j] = right_b[j];
c[i+j] = right_c[j];
j++;
}
} else if (left_a[i] < right_a[j]) {
a[i+j] = left_a[i];
b[i+j] = left_b[i];
c[i+j] = left_c[i];
i++;
} else {
a[i+j] = right_a[j];
b[i+j] = right_b[j];
c[i+j] = right_c[j];
j++;
}
}
return;
}
void update( int i, int val ){
node elem;
elem.u=i;
elem.w=val;
if(!heap_list[i])
heap_insert(heap,&elem,&heap_size,heap_list);
else
heap_update(heap,&elem,heap_list,heap_size);
return;
}
int get_i(int*a,int num,int size){
if(size==0)
return 0;
if(num>med(a,size))
return get_i(&a[(size+1)>>1],num,size>>1)+((size+1)>>1);
else
return get_i(a,num,(size-1)>>1);
}
int med(int*a,int size){
return a[(size-1)>>1];
}
void heap_insert(node *heap,node *elem,int *size,int *heap_list){
(*size)++;
int index=(*size);
while(index>1 && elem->w>heap[index/2].w){
heap[index]=heap[index/2];
heap_list[heap[index].u]=index;
index/=2;
}
heap[index]=(*elem);
heap_list[elem->u]=index;
return;
}
void heap_update(node *heap,node *elem,int *heap_list,int size){
int index=heap_list[elem->u];
while(index>1 && elem->w>heap[index/2].w){
heap[index]=heap[index/2];
heap_list[heap[index].u]=index;
index/=2;
}
while(index*2<=size && elem->w<heap[index*2].w || index*2+1<=size && elem->w<heap[index*2+1].w){
if(index*2+1<=size)
index=(heap[index*2].w<heap[index*2+1].w)?index*2+1:index*2;
else
index=index*2;
heap[index/2]=heap[index];
heap_list[heap[index].u]=index/2;
}
heap[index]=(*elem);
heap_list[elem->u]=index;
return;
}```