In this HackerEarth AltF4 and the beetles problem solution It is a nice winter Sunday morning and AltF4, our hero, decides to play a new video game. The game is called Appearism. There are a total of N beetles in the game that are initially peeping out of the grooves to look for a chance to tease you.Each one appears out of their groves at an absolute time Pi, tease AltF4 for a time duration and then go back to their groves and sleep forever at time Qi.

AltF4 has just got one shot of the nuclear weapon that ha can use to destroy all the beetles. Being very clever, he has noted down the (Pi, Qi) for each of the beetles. He also observed that the beetles are hurt by a amount A when they are looking for a chance to tease you in the groove (i.e. when time is < Pi), by B when they are out of their grooves teasing you (between Pi, Qi) and by C when they are back into the grooves and sleeping forever (when time is > Qi). Obviously B is always greater than both A and C. AltF4 being poor in math and computing asks you for favor.


HackerEarth AltF4 and the beetles problem solution


HackerEarth AltF4 and the beetles problem solution.

import java.util.*;
import java.math.*;
import java.io.*;

public class Beetles
{
public static void main(String args[])throws Exception
{
Scanner in=new Scanner(System.in);
PrintWriter out=new PrintWriter(System.out);
int t, i, j;
t = in.nextInt();
int P[] = new int[100000 + 1], Q[] = new int[100000 + 1];
while(t-- > 0) {
int N = in.nextInt();
long A = in.nextInt(), B = in.nextInt(), C = in.nextInt();

for(i=0;i<N;i++) {
P[i] = in.nextInt();
Q[i] = in.nextInt();
}
P[N] = Q[N] = Integer.MAX_VALUE;
Arrays.sort(P);
Arrays.sort(Q);
i = 0;j = 0;
long current = N * A;
long answer = current;
while(i < N || j < N) {
if(P[i] <= Q[j]) {
current += B - A;
i++;
} else {
current += C - B;
j++;
}
answer = Math.max(answer, current);
}
out.println(answer);
}

out.flush();
}
}

Second solution

#include <bits/stdc++.h>

#define sgn(x,y) ((x)+eps<(y)?-1:((x)>eps+(y)?1:0))
#define rep(i,n) for(auto i=0; i<(n); i++)
#define mem(x,val) memset((x),(val),sizeof(x));
#define rite(x) freopen(x,"w",stdout);
#define read(x) freopen(x,"r",stdin);
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
#define sqr(x) ((x)*(x))
#define pb push_back
#define clr clear()
#define inf (1<<28)
#define ins insert
#define xx first
#define yy second
#define eps 1e-9

typedef long long i64;
typedef unsigned long long ui64;
typedef string st;
typedef vector < int > vi;
typedef vector < st > vs;
typedef map < int , int > mii;
typedef map < st , int > msi;
typedef set < int > si;
typedef set < st > ss;
typedef pair < int , int > pii;
typedef vector < pii > vpii;

#define mx 0

int readInteger( int lo, int hi, st var = "" ) {
int ret ;
scanf("%d",&ret);
if( lo <= ret && ret <= hi ) return ret;
cerr << var << " is not in range [ " << lo << ", " << hi << " ] " << endl;
throw ;
}

int main(){
//read("in.txt");
int T = readInteger( 1, 50, "T" );
while( T-- ) {
int N = readInteger( 1, 20000, "N" );
int A = readInteger( 0, 1000000000, "A" );
int B = readInteger( 0, 1000000000, "B" );
int C = readInteger( 0, 1000000000, "C" );

assert( A < B && C < B );

vector< pair< int , bool > > Vec;

rep( i , N ) {
int P = readInteger( 0, 1000000000, "P" );
int Q = readInteger( 0, 1000000000, "P" );

Vec.pb( { P, 0 } );
Vec.pb( { Q, 1 } );

assert( P <= Q );
}

sort( all( Vec ) );

int cA = N, cC = 0, i = 0;

i64 ans = 1LL * N * A;

while( i < sz( Vec ) ) {
int j = i;
while( j < sz( Vec ) && Vec[i] == Vec[j] ) {
j++;
if( Vec[i].yy ) cC++;
else cA--;
}
i = j;

ans = max( ans , 1LL * cA * A + i64( N - cA - cC ) * B + 1LL * cC * C );
}

if( ans == 20000000000000ll ) throw;

printf("%lld\n", ans);
}
return 0;
}