• API
• FAQ
• Tools
• Trends
• Archive
daily pastebin goal
41%
SHARE
TWEET

# Untitled

a guest Jul 6th, 2017 134 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
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top