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)
                            LFs.add(fg);
                        else
                            RFs.add(fg);
                    } );

                    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 ) {
                result.add(this);
                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)) {
                    precessedFreqs.add(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;
                }

                precessedFreqs.add(ff.f);

                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

        // Load fighters with Fs
        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();

            fighters.add( new Fighter(y,f) );

            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) {
                        singleFFs.add( ent.getValue().get(0).y );
                        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;

            res.add(ffn);
        }

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

inline int read(){
    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];
vii ask[N];
vi huges;
int ans[N];
int q;
vi here[N];

void get_damn_input(){

    int n = read();
    q = read();
    read();

    FOR(i,n){
        read();
        a[i].fi = read();
        a[i].se = read();
        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;
        read();
        eprintf("query %d , %d\n",l,r);
        assert(r < N);
        ask[r].pb(ii(l,i));
    }

}

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;
        foreach(it,ask[r]){
            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 add(int x);
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)
    add(--cl);
  while(cr<y)
    add(cr++);
  while(cr>y)
    removee(--cr);
  return;
}
void add(int x){
  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;
}