## Algorithm

Problem Name: Data Structures - Starfleet

In this HackerRank in Data Structures - Starfleet solutions,

In a galaxy far away, there is a constant battle between the republic and the droid army. The droid army decided to launch their final attack on the republic. They have N space-fighters.

Initially the ith fighter is located at (xi, yi). All of the space-fighters move with constant velocity V units/sec in the positive X direction. i.e., fighter at (xi, yi) moves to (xi+V, yi) in 1 second. The ith space-fighter broadcasts enemy information at a frequency fi.

The republic is not scared of the artificially intelligent droid force as they have Yoda. Yoda has a special power, at any time T he can choose a region of the droid army and block one specific frequency F. This power has one constraint; it can be applied only in the form of a two sided unbounded axis parallel rectangular box open towards the both the directions across X axis (refer image below for clarity). If a frequency (F) is blocked all the space-fighters in the region having the frequency F can’t communicate.

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 are the bounds on y-axis inside which YODA can block a frequency at time T. In the region described by the query, after a time T seconds from the start, if Yoda can chose one frequency (F) he wishes to, what is the maximum number of communications he can block?

Input Format
Each test case is described as follows; the first line contains 3 space separated integers N - the number of space-fighters, Q - the number of queries you have to answer, and V - the velocity of the space-fighters separated by a single space.

N lines follow, each containing 3 space separated integers xi, yi, and fi, denoting the x co-ordinate, y co-ordinate and the frequency at which the ith ship broadcasts respectively. Each of the next Q lines contain 3 space separated integers representing YU, YD, T respectively. Refer the figure for more clarity

Note: Points on the boundaries should be counted as well.

Output Format
For each query you are to output a single integer denoting the result.

Constraints
1 <= N <= 50000
1 <= Q <= 30000
1 <= V <= 10000
-109 <= xi <= 109
-109 <= yi <= 109
1 <= fi <= 109
-109 <= YU <= 109
-109 <= YD <= 109
1 <= T <= 10000
YU >= YD

Sample Input

``````5 5 82
-4 1 4
-3 -2 2
-3 5 1
0 -5 2
1 -1 2
1 -1 57
-2 -5 11
5 -5 40
-1 -5 16
5 -1 93
``````

Sample Output

``````1
2
3
3
1
``````

Explanation Consider the points ships in the Y-range 1 to -1, they are the (-4, 1) and (1, -1), and both operate on different frequencies, hence the most times a frequency is repeated is once.

## Code Examples

### #1 Code Example with C Programming

```Code - 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->ww;
heap_list[elem->u]=index;
return;
}
``````
Copy The Code &

### #2 Code Example with C++ Programming

```Code - 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 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;
}
``````
Copy The Code &

### #3 Code Example with Java Programming

```Code - 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 > 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 > 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 > LData = new HashMap<>();
Map< Integer, List > RData = new HashMap<>();
int cy = (ry+ly)/2;

for ( Map.Entry <  Integer, List > ent : data.entrySet() ) {
int f = ent.getKey();
ArrayList 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 > yyData = new HashMap<>();
for ( Map.Entry< Integer, List > ent : sourceData.entrySet() ) {
int f = ent.getKey();
List < Fighter> ff = ent.getValue().stream().filter( fighter -> fighter.y>=y1 && fighter.ycy ) {
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 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  singleFFs = new TreeSet<>();

// Let's build the index from the ships
Map <  Integer, List > 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();
}
}
}
``````
Copy The Code &

### #4 Code Example with Python Programming

```Code - 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')
``````
Copy The Code &