All Tracks Data Structures Advanced Data Structures Segment Trees Problem

Vasya vs Rhezo
Tag(s):

Data Structures, Easy-Medium

Problem
Editorial
Analytics

Queen Vasya is preparing for a war against Rhezo. She has N warriors in total arranged in a line. Let us number the warriors by numbers from 1 to N. She will fight Rhezo's army for Q days, and each day she can choose only one warrior.

For each warrior, we know 2 values associated with him, let us call these A and B. Each day Vasya can choose her warrior from a range \(L_i\) to \(R_i\), she must choose the warrior with maximum A value. If there is more than 1 warrior having the same maximum A value, she chooses the warrior with minimum B value. If still there is more than 1 warrior with same maximum A value and same minimum B value, she chooses the one with lower index in line.

You being the hand of Queen Vasya, need to help her in choosing the warrior for each day.

Input:

First line contains a single integer N, denoting the number of warriors Queen Vasya has. Second line contains N space separated integers \(A_i\). Third line contains N space separated integers \(B_i\). Next line contains a single integer Q, denoting the number of days Queen Vasya chooses a warrior. Each of the next Q lines contains 2 integers \(L_i\) and \(R_i\).

Output:

For each \(L_i\) and \(R_i\), print the index of the warrior that Queen Vasya should choose.

Constraints:

\(1 \le N, Q \le 10^6\)

\(1 \le A_i, B_i \le 10^9\)

\(1 \le L_i \le R_i \le N\)

SAMPLE INPUT
5
1 8 4 6 8
4 8 6 3 7
4
1 4
2 4
3 4
1 5
SAMPLE OUTPUT
2
2
4
5
Explanation

For the last query, both warrior number 2 and warrior number 5 have the same maximum A value, but we will choose warrior 5 because he has a lower B value.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

Lenskart

Challenge Name

Lenskart Java Hiring Challenge

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?