Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.BufferedReader;
- import java.io.IOException;
- import java.io.InputStreamReader;
- import java.util.Comparator;
- import java.util.PriorityQueue;
- class SubarrayFunctions {
- static int[] a = new int[2001];//1 Based indexing is used
- public static void main(String[] args) throws IOException {
- BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
- int t, n, m, p;
- String[]s;
- t = Integer.parseInt(br.readLine());
- while (t-- > 0) {
- s = br.readLine().split("\\s");
- n = Integer.parseInt(s[0]);
- m = Integer.parseInt(s[1]);
- p = Integer.parseInt(s[2]);
- s = br.readLine().split("\\s");
- for (int i = 1; i <=n; i++) {
- a[i] = Integer.parseInt(s[i-1]);
- }
- System.out.println(solve(a, n, m, p));
- }
- }
- private static String solve(int[] a, int n, int m, int p) {
- PriorityQueue<Integer> minQueue = new PriorityQueue<>();
- PriorityQueue<Integer> maxQueue = new PriorityQueue<>(Comparator.reverseOrder());
- int ans = Integer.MIN_VALUE, l = 0, r = 0, mSmallestXor, pLargestXor;
- int maxMP = Integer.max(m, p);
- for (int i = 1,j; i <=n-maxMP+1; i++) {
- maxQueue.add(a[i]);
- minQueue.add(a[i]);
- mSmallestXor = a[i];
- pLargestXor = a[i];
- int tempAns;
- for (j = i + 1; j <=n; j++) {
- if (minQueue.size() < p) {
- minQueue.add(a[j]);
- pLargestXor ^= a[j];
- }
- else {
- if (minQueue.peek() < a[j]) {
- int x = minQueue.poll();
- minQueue.offer(a[j]);
- pLargestXor ^= x;
- pLargestXor ^= a[j];
- }
- }
- if (maxQueue.size() < m) {
- maxQueue.add(a[j]);
- mSmallestXor ^= a[j];
- }
- else {
- if (maxQueue.peek() > a[j]) {
- int x = maxQueue.poll();
- maxQueue.offer(a[j]);
- mSmallestXor ^= x;
- mSmallestXor ^= a[j];
- }
- }
- if (minQueue.size()>=p && maxQueue.size()>=m){
- tempAns = mSmallestXor & pLargestXor;
- if (ans < tempAns) {
- ans = tempAns;
- l = i;
- r = j;
- } else if (ans == tempAns) {
- if ((j - i + 1) > (r - l + 1)) {
- l = i;
- r = j;
- }
- }
- }
- }
- j--;
- tempAns = mSmallestXor & pLargestXor;
- if (ans < tempAns) {
- ans = tempAns;
- l = i;
- r = j;
- } else if (ans == tempAns) {
- if ((j - i + 1) > (r - l + 1)) {
- l=i;
- r = j;
- }
- }
- minQueue.clear();
- maxQueue.clear();
- }
- return l + " " + r + " " + ans;
- }
- }
Add Comment
Please, Sign In to add comment