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