SHARE
TWEET

Untitled

a guest Jul 6th, 2017 127 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. Our dear Spiderman has fallen in love with Mary Jane and is planning to propose her tonight.
  2. He has thought of a wonderful way which would require the entire evening and thus can't be disturbed.
  3. As usual, a problem has occurred and this time Spiderman wants your help to solve the problem.
  4. Can you help him?
  5. You will be given an array A of size N and Q queries.
  6. In every query, you will be given 4 integers E,F,G and H.
  7. Consider every permutation of subarray A[E] to A[F], similarly consider every permutation of subarray A[G] to A[H].
  8. You have to tell whether there exists any permutation of both subarrays such that, the number of positions where A[i]!=A[j], where E <= i <= F and G <= j <= H is atmost 1.Both permutations can be different.Every query is independent.
  9. The equality F-E+1 = H-G+1 always holds.
  10.  
  11. Input
  12.  
  13.     First line contains T, the number of test cases.
  14.     For every test case, the first line contains two integers N, the size of array and Q, the number of queries respectively.
  15.     The next line contains N space separated integers.
  16.     The next Q lines contains four integers E,F,G and H respectively, describing the query, as stated above.
  17.  
  18.  
  19.  
  20. Output
  21. For each query, output the required answer ("YES" or "NO") in a new line.
  22.  
  23. Constraints
  24.  
  25.     1 <= T <= 5
  26.     1 <= N,Q <= 105
  27.     1 <= A[i] <= 105
  28.     1 <= E,G <=F,H <= N
  29.  
  30.  
  31. Sample Test Case
  32.  
  33. Input
  34.  
  35. 1
  36. 8 2
  37. 1 2 3 4 1 1 2 3
  38. 1 2 3 4
  39. 1 4 5 8
  40.  
  41.  
  42. Output
  43.  
  44. NO
  45. YES
  46.  
  47. Explanation
  48.  
  49. For query 1 2 3 4 there exists no such permutation, thus answer is NO.
  50. For query 1 4 5 8, one such permutation is
  51. 1 2 3 4
  52. 1 2 3 1
  53. Here the difference is 1, thus answer is YES.
RAW Paste Data
Top