Algorithm
Problem Name: Data Structures -
In this HackerRank in Data Structures -
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 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->ww;
heap_list[elem->u]=index;
return;
}
#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;
}
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;
}
#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)
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 > 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)) {
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 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) {
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();
}
}
}
#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')