problem.txt (2163B)
1 C. Maximize the Score 2 time limit per test2 seconds 3 memory limit per test256 megabytes 4 You are given an array a 5 of length 2n 6 . Each integer from 1 7 to n 8 occurs exactly twice in a 9 . 10 11 Initially, your score is 0 12 . 13 14 You can repeatedly perform the following operation while a 15 is non-empty: 16 17 Choose an integer x 18 that is present in a 19 . 20 Let l 21 and r 22 be the indices of the leftmost and rightmost occurrences of x 23 in the current array, respectively. If x 24 occurs only once, then l=r 25 . 26 Add (r−l+1)2 27 to your score. 28 Delete the elements al,al+1,…,ar 29 from a 30 . The remaining elements are concatenated without changing their order and re-indexed starting from 1 31 . 32 Find the maximum possible score after making the array empty. 33 34 Input 35 Each test contains multiple test cases. The first line contains the number of test cases t 36 (1≤t≤104 37 ). The description of the test cases follows. 38 39 The first line of each test case contains a single integer n 40 (1≤n≤2⋅105 41 ). 42 43 The second line contains 2n 44 integers a1,a2,…,a2n 45 (1≤ai≤n 46 ). 47 48 It is guaranteed that each integer from 1 49 to n 50 occurs exactly twice in a 51 . 52 53 It is guaranteed that the sum of n 54 over all test cases does not exceed 2⋅105 55 . 56 57 --- 58 59 - array a, size 2n 60 - include each number from 1->n twice 61 - score := 0 62 - while a isn't empty you can do these steps if you want: 63 - choose an int x in a 64 - l = leftmost index of int x, r = rightmost index of int x 65 - iff only one x then l == r 66 - add (r - l + 1) ^ 2 to score 67 - delete a_l, a_l+1, ... a_r from array 68 69 --- 70 71 examples: 72 73 --- 74 75 ex1 76 77 1 1 78 79 drop 1, (r - l+1) ^ 2 = 4 80 score = 4 81 82 --- 83 84 ex2 85 86 1 2 1 2 87 88 3-1 + 1 = 3 89 90 3**2 = 9 91 92 (0 - 0+1) ** 2 = 1 93 94 res=10 95 96 this could also be considered the spread with the largest score. 97 98 --- 99 100 1 2 2 1 101 102 (3 - 0 + 1) ^ 2 = 16 103 104 differ from inner first: 105 106 (2 - 1 + 1) ^ 2 = 4 107 (1 - 0 + 1) ^ 2 = 4 108 109 = 8 110 111 --- 112 113 1 1 2 3 3 2 114 115 (5 - 2 + 1) ^ 2 = 16 116 117 1 1 118 119 (1 - 0 + 1) ^ 2 = 4 120 121 = 20 122 123 124 --- 125 126 1 2 3 3 2 1 127 128 (5 - 0 + 1) ^ 2 = 36 129 130 131 --- 132 133 1 2 3 4 1 2 3 4 134 135 (4 - 0 + 1) ^ 2 = 25 136 137 2 3 4 138 139 (0 - 0 + 1) ^ 2 = 1 140 (0 - 0 + 1) ^ 2 = 1 141 (0 - 0 + 1) ^ 2 = 1 142 143 25 + 3 = 28 144 145 it'd be equivalent to remove in either order so just remove first I guess