Mr. X and His Shots

                            Solution in C :

In C++ :




#include <iostream>
#include <vector>
#include <algorithm>

using namespace std ;

struct segment 
{
    bool isleft ;
    int point ;
    bool isfielder ;
} ;
vector < segment > v ( 400010 ) ;
vector < segment > :: iterator it ;

bool cmpr ( segment & a , segment & b )
{
    if ( a.point != b.point )
    {
        return a.point < b.point ;
    }
    if ( a.isleft != b.isleft )
    {
        return a.isleft ;
    }
    return ! ( a.isfielder ) ;
}

int main ()
{
    int n , m ;
    cin >> n >> m ;
    int counter = 0 ;
    for ( int i = 0 ; i < n ; i ++ )
    {
        int a , b;
        cin >> a >> b ;
        segment temp ;
        temp.isleft = true ;
        temp.point = a ;
        temp.isfielder = false ;
        v [ counter ++ ] = temp ;
        temp.isleft = false ;
        temp.point = b ;
        v [ counter ++ ] = temp ;
    }
    for ( int i = 0 ; i < m ; i ++ )
    {
        int a , b;
        cin >> a >> b ;
        segment temp ;
        temp.isleft = true ;
        temp.point = a ;
        temp.isfielder = true ;
        v [ counter ++ ] = temp ;
        temp.isleft = false ;
        temp.point = b ;
        v [ counter ++ ] = temp ;
    }
    it = v.begin () ;
    advance ( it , counter ) ;
    sort ( v.begin () , it , cmpr ) ;       // segment intersection problem 
    int bat = 0 , field = 0 ;
    long long int ans = 0 ;
    for ( int i = 0 ; i < counter ; i ++ )
    {
        if ( v [ i ].isleft == true )
        {
            if ( v [ i ].isfielder )
            {
                ans += bat ;                // intersects with all the batsman 
                field ++ ;
            }
            else 
            {
                ans += field ;
                bat ++ ;
            }
        }
        else
        {
            if ( v [ i ].isfielder )
            {
                field -- ;    
            }
            else
            {
                bat -- ;    
            }
        }
    }
    cout << ans ;
    return 0 ;
}








In  Java :






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

public class Solution {
    public static int binarySearch(long[] arr, long num) {
        int head = 0, tail = arr.length - 1;
        while (head <= tail) {
            int mid = (head + tail) / 2;
            if (arr[mid] <= num) {
                head = mid + 1;
            } else {
                tail = mid - 1;
            }
        }
        return head;
    }
    public static long strenth(long[] heads, long[] tails, long C, long D) {
        long result = heads.length;
        result -= (heads.length - Solution.binarySearch(heads, D));
        result -= (tails.length - Solution.binarySearch(tails, -C));
        return result;
    }

    public static void main(String[] args) {
      
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(), M = sc.nextInt();
        long[] A = new long[N], B = new long[N];
        for (int i = 0; i < N; i++) {
            A[i] = sc.nextLong(); B[i] = -sc.nextLong();
        }
        Arrays.sort(A); Arrays.sort(B);
        long sum = 0L;
        for (int i = 0; i < M; i++) {
            sum += Solution.strenth(A, B, sc.nextLong(), sc.nextLong());
        }
        System.out.println(sum);
    }
}







In C :




#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#define _DEBUG_     0
typedef struct sRange {
    int s;
    int e;
} Range;

int cmpfunc(const void *a, const void *b) {
    Range *this = (Range *)a;
    Range *that = (Range *)b;
    if (this->s > that->s) return 1;
    if (this->s < that->s) return -1;
    return this->e - that->e;
}

__inline__ int overLaps(Range *a, Range *b) {
    if ((a->s <= b->e) && (a->e >= b->s)) return 1;
    return 0;
}
int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */
    int N = 0, M = 0, A = 0, B = 0, C = 0, D = 0, i = 0, j = 0;
    int S = 0;
    scanf("%d %d", &N, &M);
    Range *shots = (Range *)malloc(N * sizeof(Range));
    Range *field = (Range *)malloc(M * sizeof(Range));
    for (i = 0; i < N; i++) {
        scanf("%d %d", &A, &B);
        shots[i].s = A;
        shots[i].e = B;
    }
    qsort(shots, N, sizeof(Range), cmpfunc);
    #if 0 //_DEBUG_
    for (i = 0; i < N; i++) {
        printf("%d %d\n", shots[i].s, shots[i].e);
    }
    #endif
    // get fielders
    for (i = 0; i < M; i++) {
        scanf("%d %d", &C, &D);
        field[i].s = C;
        field[i].e = D;
    }
    qsort(field, M, sizeof(Range), cmpfunc);
    // Keep moving fielder and shot together
    i = 0;
    j = 0;
    while (i < M && j < N) {
        if (field[i].e < shots[j].s) i++; // increment fielder
        else if (field[i].s > shots[j].e) j++; //increment shot
        else {
            // they are overlapping, check all the shots
            int tempJ = j;
            while (tempJ < N && shots[tempJ].s <= field[i].e) {
                if (overLaps(&shots[tempJ], &field[i])) {
                    S++;
                }
                tempJ++;
            }
            i++;
        }
        #if _DEBUG_
        printf("s %d, f %d, S %d\n", j, i, S);
        #endif
    }
    printf("%d\n", S);
    return 0;
}









In Python3 :






import sys
import os

# STEP 1: Take in parameters:
firstLine = input().split()
N = int(firstLine[0])
M = int(firstLine[1])

maxVal = 1000000
tally1 = [0] * maxVal
tally2 = [0] * maxVal

# STEP 2: Take in the ranges of the shots:
for i in range(0,N):
    line = input().split()
    tally1[int(line[0])] += 1
    tally2[int(line[1]) + 1] -= 1
    
# STEP 3: Tally the strengths of the players:
for i in range(1,maxVal):
    tally1[i] += tally1[i-1]
    tally2[i] += tally2[i-1]

sumStrengths = 0

for j in range(0,M):
    player = input().split()
    playerStart = int(player[0])
    playerEnd = int(player[1])       
    sumStrengths += tally1[playerEnd] + tally2[playerStart]
            
print(sumStrengths)