Resource constraints

Time limit: 1.0s   Memory limit: 256.0MB

Given three integer arrays
　　A = [A1, A2, ... AN],
　　B = [B1, B2, ... BN],
　　C = [C1, C2, ... CN]，
Please count how many triples (i, j, k) satisfy:
　　1. 1 <= i, j, k <= N
　　2. Ai < Bj < Ck

Input format

The first line contains an integer N.
The second line contains N integers A1, A2,... An.
The third line contains N integers B1, B2,... BN.
The fourth line contains N integers C1, C2,... CN.

For 30% of data, 1 < = n < = 100
For 60% of the data, 1 < = n < = 1000
For 100% data, 1 < = n < = 100000 0 < = AI, Bi, CI < = 100000

Output format

An integer represents the answer

sample input

3
1 1 1
2 2 2
3 3 3

sample output

27

Problem solving ideas: (before optimization)

To find an array from each of the three rows into an increasing sequence, the most violent way is to find it in turn in a triple loop, but because of 10w data, the triple loop certainly won't work.

You can turn all three arrays into ordered arrays before processing. On the basis of double for, optimize the third for: treat the second for and the third for as double pointers, so that the third for only moves to the right without fallback. That is, the final complexity is dual. But eventually it will time out, and one or two test points can't pass.

java code: (before optimization)

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

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		List<Integer> list1 = new ArrayList<>(n);
		List<Integer> list2 = new ArrayList<>(n);
		List<Integer> list3 = new ArrayList<>(n);
		String[] split = br.readLine().split(" ");
		for(int i = 0; i < split.length; i++) {
			list1.add(Integer.parseInt(split[i]));
		}
		split = br.readLine().split(" ");
		for(int i = 0; i < split.length; i++) {
			list2.add(Integer.parseInt(split[i]));
		}
		split = br.readLine().split(" ");
		for(int i = 0; i < split.length; i++) {
			list3.add(Integer.parseInt(split[i]));
		}
		Collections.sort(list1);
		Collections.sort(list2);
		Collections.sort(list3);
		long ans = 0;
		for(int i = 0; i < n; i++) {
			int k = 0;
			for(j = 0; j < n; j++) {
				if(list2.get(j) <= list1.get(i)) {
					continue;
				}
				for(; k < n; k++) {
					if(list3.get(k) > list2.get(j)) {
						ans += n - k;
						break;
					}
				}
			}
		}
		System.out.println(ans);
	}
}

Submit screenshot: (card the last test point)  

Optimization ideas:

Using the double pointer idea, the double for is optimized to have only one for. It is necessary to take the second for as the benchmark, and move the pointers of the first for and the third for all the time without going back. Specifically, every time the second for is moved, as long as the value pointed by the pointer in the first for is less than the value pointed by the second for, move the pointer of the first for backward. Similarly, as long as the third F If the value of or is less than or equal to the value of the second for, move the pointer of the third for backward. The element product of each move (with some processing) is the final partial solution. The cumulative output is sufficient. Since the final result will be very large, it needs to be defined as long.

java code: (after optimization)

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

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		List<Integer> list1 = new ArrayList<>(n);
		List<Integer> list2 = new ArrayList<>(n);
		List<Integer> list3 = new ArrayList<>(n);
		String[] split = br.readLine().split(" ");
		for(int i = 0; i < split.length; i++) {
			list1.add(Integer.parseInt(split[i]));
		}
		split = br.readLine().split(" ");
		for(int i = 0; i < split.length; i++) {
			list2.add(Integer.parseInt(split[i]));
		}
		split = br.readLine().split(" ");
		for(int i = 0; i < split.length; i++) {
			list3.add(Integer.parseInt(split[i]));
		}
		Collections.sort(list1);
		Collections.sort(list2);
		Collections.sort(list3);
		long ans = 0;
		
		int i = 0, k = 0;
		for(int j = 0; j < n; j++) {
			while(i < n && list1.get(i) < list2.get(j)) i++;
			while(k < n && list2.get(j) >= list3.get(k)) k++;
			ans += (long)i * (n - k);
		}
		System.out.println(ans);
	}
}

Submit screenshot: