Guest User

Untitled

a guest
Nov 19th, 2017
113
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 3.36 KB | None | 0 0
  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4. import java.util.Comparator;
  5. import java.util.PriorityQueue;
  6.  
  7. class SubarrayFunctions {
  8.  
  9.     static int[] a = new int[2001];//1 Based indexing is used
  10.  
  11.     public static void main(String[] args) throws IOException {
  12.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  13.         int t, n, m, p;
  14.         String[]s;
  15.         t = Integer.parseInt(br.readLine());
  16.         while (t-- > 0) {
  17.             s = br.readLine().split("\\s");
  18.             n = Integer.parseInt(s[0]);
  19.             m = Integer.parseInt(s[1]);
  20.             p = Integer.parseInt(s[2]);
  21.  
  22.             s = br.readLine().split("\\s");
  23.             for (int i = 1; i <=n; i++) {
  24.                 a[i] = Integer.parseInt(s[i-1]);
  25.             }
  26.             System.out.println(solve(a, n, m, p));
  27.         }
  28.     }
  29.  
  30.     private static String solve(int[] a, int n, int m, int p) {
  31.  
  32.         PriorityQueue<Integer> minQueue = new PriorityQueue<>();
  33.         PriorityQueue<Integer> maxQueue = new PriorityQueue<>(Comparator.reverseOrder());
  34.         int ans = Integer.MIN_VALUE, l = 0, r = 0, mSmallestXor, pLargestXor;
  35.         int maxMP = Integer.max(m, p);
  36.         for (int i = 1,j; i <=n-maxMP+1; i++) {
  37.             maxQueue.add(a[i]);
  38.             minQueue.add(a[i]);
  39.             mSmallestXor = a[i];
  40.             pLargestXor = a[i];
  41.             int tempAns;
  42.             for (j = i + 1; j <=n; j++) {
  43.                 if (minQueue.size() < p) {
  44.                     minQueue.add(a[j]);
  45.                     pLargestXor ^= a[j];
  46.                 }
  47.                 else {
  48.                     if (minQueue.peek() < a[j]) {
  49.                         int x = minQueue.poll();
  50.                         minQueue.offer(a[j]);
  51.                         pLargestXor ^= x;
  52.                         pLargestXor ^= a[j];
  53.                     }
  54.                 }
  55.                 if (maxQueue.size() < m) {
  56.                     maxQueue.add(a[j]);
  57.                     mSmallestXor ^= a[j];
  58.                 }
  59.                 else {
  60.                     if (maxQueue.peek() > a[j]) {
  61.                         int x = maxQueue.poll();
  62.                         maxQueue.offer(a[j]);
  63.                         mSmallestXor ^= x;
  64.                         mSmallestXor ^= a[j];
  65.                     }
  66.                 }
  67.  
  68.                 if (minQueue.size()>=p && maxQueue.size()>=m){
  69.                     tempAns = mSmallestXor & pLargestXor;
  70.                     if (ans < tempAns) {
  71.                         ans = tempAns;
  72.                         l = i;
  73.                         r = j;
  74.                     } else if (ans == tempAns) {
  75.                         if ((j - i + 1) > (r - l + 1)) {
  76.                             l = i;
  77.                             r = j;
  78.                         }
  79.                     }
  80.  
  81.                 }
  82.             }
  83.             j--;
  84.             tempAns = mSmallestXor & pLargestXor;
  85.             if (ans < tempAns) {
  86.                 ans = tempAns;
  87.                 l = i;
  88.                 r = j;
  89.             } else if (ans == tempAns) {
  90.                 if ((j - i + 1) > (r - l + 1)) {
  91.                     l=i;
  92.                     r = j;
  93.                 }
  94.             }
  95.             minQueue.clear();
  96.             maxQueue.clear();
  97.  
  98.         }
  99.         return l + " " + r + " " + ans;
  100.     }
  101. }
Add Comment
Please, Sign In to add comment