Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

dreamplayDaddy's blog

By dreamplayDaddy, history, 11 months ago, In English,

I have a vector of pairs of length N. Now i have Q queries of type, given range let say L to R, find the minimum value of second element of pair whose first element is equal to given number K.

For example : vector of 6 elements [{2,5},{8,7},{2,3},{8,6},{2,1},{8,4}] Now for query : L=3 R=6 (1-based indexing) and K=8

Answer would be -> 4 which corresponds to this pair {8,4}

There are 10^5 queries and N can be upto 10^5.

can someone give me an idea how to approach this problem more efficiently?

Read more »

 
 
 
 
  • Vote: I like it
  • +9
  • Vote: I do not like it