#P17552. [JAG 2026 Summer Camp #2] Empty Intersection
[JAG 2026 Summer Camp #2] Empty Intersection
Problem Description
You are given two integer sequences and , and two sequences of positive integers and . All four sequences have length .
Choose two (possibly empty) intervals of indices, for and for . Here, are integers satisfying and .
Let and be the sets of values occurring in these intervals, respectively:
The chosen intervals must satisfy . In other words, no value may occur in both intervals.
If , the interval of is empty and . Likewise, if , the interval of is empty and .
The score of the two chosen intervals is
Find the maximum possible score among all valid choices.
Input Format
The input contains one or more test cases. The first line of the input contains an integer (), which is the number of test cases. The descriptions of the test cases follow, each in the format below.
N
A_1 A_2 ... A_N
B_1 B_2 ... B_N
V_1 V_2 ... V_N
W_1 W_2 ... W_N
The first line contains a single integer , the common length of the four sequences ().
The following four lines contain integers each and describe the sequences , , , and , respectively.
The integers and satisfy for every ().
The integers and satisfy for every ().
The sum of over all test cases does not exceed .
Output Format
Output lines. The -th line should contain the maximum possible score for the -th test case.
4
3
1 2 3
3 2 1
3 4 5
6 2 1
3
1 1 1
1 1 1
2 3 4
5 5 5
4
1 2 1 3
4 2 4 3
5 6 5 1
4 10 4 10
5
3 1 2 4 3
1 1 2 2 4
1 3 3 2 1
2 2 3 1 1
13
15
33
11
Hint
In the first test case, we can choose the interval of and the interval of . More precisely, we can set , , , and . Their sets of values are and , respectively, and they are disjoint. The score is
which is the maximum possible score.
In the second test case, we can choose an empty interval of and the entire interval of . More precisely, , , , and .