Dr. Programmer

After the death of Tony Stark now it's time for Morgon Stark to save the world. So she decided to build a data-centre in City. Assuming house of Morgon Stark at origin in 2D-plane she wants that distance of data-centre should be not more than Z from her house. But she has limited number of choices where she can build data-centre.She is interested to know that how many ways  she can choose a location for her data-centre.  So she gave her problem to you and asked for your help. Although you are not Dr. Strange , you  are Dr. Programmer so you can solve her problem.

You are given a set of X coordinates having length N  and a set of Y coordinates having length M  , find how many ways you can choose A point P(X0,Y0) from given set such that

• X0 is one of the given X-coordinates.
• Y0 is one of the given Y-coordinates.
•  Manhattan distance of P(X0,Y0) is less than or equal to Z  . 

You are given 3 types of query

Z A L1 R1 :  you can choose X0 between [L1,R1] from given set of X cordinates and no restriction on Y0

Z B L2 R2 : you can choose Y0  between [L2,R2] from given set of Y cordinates and no restriction on X0

Z C L1 R1 L2 R2 :  you can choose X0  between [L1,R1] from given set of X cordinates  and Y0 between [L2,R2] from given set of Y cordinates

Example:

Input:  4 3 5
12 7 19 18
4 6 12
18 C 7 15 3 7
20 A 10 100
15 B 4 10
100 C 1 10000 100 200
40 B 3 10
Output: 4 2 2 0 8

Approach

Java

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class DrProgrammer {
    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int t = Integer.parseInt(st.nextToken());
        long[] arrx = new long[n];
        long[] arry = new long[m];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++)
            arrx[i] = Long.parseLong(st.nextToken());

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < m; i++)
            arry[i] = Long.parseLong(st.nextToken());

        Arrays.sort(arrx);
        Arrays.sort(arry);

        while (t-- > 0) {
            st = new StringTokenizer(br.readLine());
            long z = Long.parseLong(st.nextToken());
            int count = 0, p = 0, q = 0, x = n, y = m;
            String s = st.nextToken();

            if (s.equals("A")) {
                long l1 = Long.parseLong(st.nextToken());
                long r1 = Long.parseLong(st.nextToken());
                p = lowerBound(arrx, l1);
                x = upperBound(arrx, r1);
            } else if (s.equals("B")) {
                long l2 = Long.parseLong(st.nextToken());
                long r2 = Long.parseLong(st.nextToken());
                q = lowerBound(arry, l2);
                y = upperBound(arry, r2);
            } else {
                long l1 = Long.parseLong(st.nextToken());
                long r1 = Long.parseLong(st.nextToken());
                long l2 = Long.parseLong(st.nextToken());
                long r2 = Long.parseLong(st.nextToken());
                p = lowerBound(arrx, l1);
                x = upperBound(arrx, r1);
                q = lowerBound(arry, l2);
                y = upperBound(arry, r2);
            }

            int j = y - 1;
            for (int i = p; i < x; i++) {
                while (j >= q && arrx[i] + arry[j] > z)
                    j--;
                if (j < q)
                    break;
                count += j - q + 1;
            }

            System.out.println(count);
        }
    }

    static int lowerBound(long[] arr, long k) {
        int s = 0, e = arr.length;
        while (s != e) {
            int mid = (s + e) >> 1;

            if (arr[mid] < k)
                s = mid + 1;
            else
                e = mid;
        }
        return s;
    }

    static int upperBound(long[] arr, long k) {
        int s = 0, e = arr.length;
        while (s != e) {
            int mid = (s + e) >> 1;

            if (arr[mid] <= k)
                s = mid + 1;
            else
                e = mid;
        }
        return s;
    }
}