Unusual Queries SOLUTION UNSQUERS

Unusual Queries November Challenge 2020

There are N mountains in Chefland, arranged in a line and numbered 1 through N from left to right. For each valid i, the i-th mountain from the left has a height Hi.
Chef wants to choose a contiguous sequence of mountains l,l+1,…,r and visit them in this order. He has a notebook where he writes down some heights of mountains. Initially, the notebook contains only the integer 0 and each time he visits a new mountain whose height is strictly greater than all the integers written in the notebook so far, he writes its height in the notebook. The satisfaction Chef gets from travelling is the number of positive integers written in the notebook at the end. For example, if the mountains have heights (1–,5–,2,5,3,7–,2,9–), Chef’s satisfaction is 4 and the integers written in the notebook at the end are 0,1,5,7,9.
Your task is to answer Q queries. In each query, Chef gives you two integers L and R (1≤L≤R≤N) and you should find the maximum satisfaction he can get if he can choose to visit any contiguous sequence of mountains from l to r such that L≤l≤r≤R. Note that the queries are encoded in such a way that they have to be processed online.
Input
The first line of each test case contains three space-separated integers N, Q and s.
The second line contains N space-separated integers H1,H2,…,HN.
Each of the following Q lines contains two space-separated integers x and y describing a query. The parameters L and R for this query can be computed as follows:
Let last be the answer to the previous query, or 0 if this is the first query in this test case.
Set L to (x+s⋅last−1)%N+1.
Set R to (y+s⋅last−1)%N+1.
If L>R, swap L and R.
Output
For each query, print a single line containing one integer — the maximum satisfaction Chef can get.
Constraints
1≤N,Q≤105
0≤s≤1
1≤Hi≤105 for each valid i
1≤x,y≤N
Subtasks
Subtask #1 (15 points): N≤1,000
Subtask #2 (35 points): s=0, i.e. the queries do not have to be processed online
Subtask #2 (50 points): original constraints
Example Input 1
6 3 0
4 2 3 1 5 5
1 6
2 4
3 4
Example Output 1
3
2
1
Explanation
In the first query, Chef can choose to visit a contiguous subsequence of mountains with heights (4,2,3,1,5,5). The subsequence that gives the maximum satisfaction is (2,3,1,5). In that case, Chef writes the integers 0,2,3,5 to his notebook, so the answer is 3.
In the second query, Chef can choose to visit a contiguous subsequence of mountains with heights (2,3,1). The whole sequence has the maximum satisfaction 2, since Chef writes the integers 0,2,3.
In the third query, the largest (and the only possible) satisfaction is 1, since Chef writes either 0,3 or 0,1.
Example Input 2
10 10 1
7 8 8 9 10 10 2 3 5 10
9 6
2 9
10 6
4 2
5 10
4 5
8 7
8 2
7 7
9 5
Example Output 2
3
3
3
1
4
2
2
4
1
4
 
Solution:
nqs = list(map(int , input().split()))
 
n = nqs[0]
q = nqs[1]
s = nqs[2]
 
a = list(map(int , input().split()))
 
b = arr = [[0 for i in range(n+1)] for j in range(n+1)]
 
 
for i in range(1,n+1):
    ctr = 1
    curr = a[i-1]
    b[i][i] = 1
    for j in range(i+1 , n+1):
        if(a[j-1] > curr):
            ctr += 1 
            curr = a[j-1]
        
        b[i][j] = ctr
 
    
for i in range(1,n+1):
    best = 1
    for j in range(n,0,-1):
        best = max(best , b[j][i])
        b[j][i] = best
    
for i in range(1,n+1):
    best =b[i][i]
    for j in range(i+1 , n+1):
        best = max(best , b[i][j])
        b[i][j] = best
 
last = 0
for _ in range(q):
    lr = list(map(int, input().split()))
    l  = lr[0]
    r = lr[1]
    l = (l + s*last -1)%n +1
    r = (r + s*last -1)%n +1
 
    if(l > r):
        l = l^r
        r = l^r
        l = l^r
 
    last = b[l][r]
    print(last)
 

November Challenge 2020 SOLUTION CodeChef

October Lunchtime 2020 CodeChef SOLUTIONS

RELATED :

Related :

Related :

Leave a Comment