So perfect bro!
Perfect explanation!! Thank You!!
It can be done in O(N+Q) if you store the prefix count of decreasing and increasing arrays.
Every query can be solved in O(1) without pre-computation. Wait for the official editorial
if the 0’s and 1’s are always alternating, i just called all the elements - which are common to both MIS and MDS as 0’s and then counted them in an array. Note that 0 1 1 0 would mean the first MIS or MDS is being completed at the fourth element. Hence i counted the number of sequences (as it is always alternately MIS and MDS). if it’s even, then yes, else no.
Anyone please explain the flaw or tell me why it’s failing?
It’s very simple and tricky problem, My AC solution :
n,q = map(int,input().split())
a = list(map(int,input().split()))
for _ in range(q):
l,r = map(int,input().split())
if (a[l-1]<a[l] and a[r-2]<a[r-1]) or (a[l-1]>a[l] and a[r-2]>a[r-1]):
print('NO')
else:
print('YES')
This problem can be solved very easily with a small observation. All you have to do is just count the number of times the sequence is changing from increasing to decreasing (or) decreasing to increasing in the given interval which can be very easily done with prefix arrays. Then
- If the number of times the seq changed is odd. You will have equal number of rises and falls
- If it is even then the number of rises will not be equal to falls or vice versa
Check my submission CodeChef: Practical coding for everyone
if __name__ == '__main__':
n, k = [int(__) for __ in input().strip().split()]
arr = [int(__) for __ in input().strip().split()]
di = [0]
for i in range(1, n - 1):
di.append(di[-1] + 1 if (arr[i] - arr[i - 1]) * (arr[i] - arr[i + 1]) > 0 else di[-1])
di.append(di[-1])
for _ in range(k):
a, b = [int(__) for __ in input().strip().split()]
if abs(a - b) == 1:
print("NO")
elif a == 1:
print("YES" if di[b-2] > 0 and di[b - 2] & 1 else "NO")
else:
diff = di[b - 2] - di[a - 1]
print("YES" if diff > 0 and diff & 1 else "NO")
I’ve solved each query in O(1) time. Correct me if you find anything wrong (you may find spelling mistakes as well).
Well Even I did it with same approach and the problem with your solution is in the worst case ie.(strictly increasing/decreasing sequence) the increase or decreasing while loop inside the query will travel for n times which exceed the complexity of O(log n) so instead of while use map in cpp (upper bound and Lower bound in maps )
→ my solution: CodeChef: Practical coding for everyone
I am getting WA on the test case #5 , can you please help me in finding that test case?
well I guess you have missed the condition when there is only 1 increasing/decreasing sequence in the query and by subtracting it from 1 it results in 0 (well I am not sure about this though please do a step wise iteration)