1870 - Easy xy

Cerința

Se dă un vector v cu N elemente numere naturale numerotate de la 1 la N și M întrebări de forma:

• x y p: se afișează valoarea ce s-ar afla pe poziția p dacă v[x...y] ar fi ordonat crescător.

Să se răspundă la cele M întrebări.

Date de intrare

Fișierul de intrare easyxy.in conține pe prima linie numerele N și M. Pe următoarea linie se află N elemente ce reprezintă elementele vectorului. Pe următoarele M linii se află întrebările.

Date de ieșire

Fișierul de ieșire easyxy.out va conține pe fiecare linie i răspunsul la întrebarea i, în ordinea în care acestea apar în fișierul de intrare.

Restricții și precizări

• 1 ≤ N,M ≤ 100.000
• Elementele vectorului sunt ≤ 1.000.000.000
• Pentru orice întrebare, 1 ≤ x ≤ p ≤ y ≤ N

Exemplu:

easyxy.in

6 3
1 3 2 5 6 3
1 3 2
1 6 5
3 5 4

easyxy.out

2
5
5

Rezolvare

<syntaxhighlight lang="python3"> import sys import bisect

def solve_test_case(n, m, arr):

   prefix_sums = [0] * (n + 1)
   for i in range(1, n + 1):
       prefix_sums[i] = prefix_sums[i - 1] + arr[i - 1]

   for _ in range(m):
       x, y, p = map(int, input().split())

       total_sum = prefix_sums[y] - prefix_sums[x - 1]

       left = 0
       right = total_sum

       while left <= right:
           mid = (left + right) // 2

           count_less = bisect.bisect_left(prefix_sums, mid)

           if count_less < p:
               left = mid + 1
           else:
               right = mid

       answer = right

       print(answer)

def main():

   n, m = map(int, input().split())

   arr = list(map(int, input().split()))

   for _ in range(m):
       solve_test_case(n, m, arr)

if __name__ == "__main__":

   sys.stdin = open("easyxy.in")
   sys.stdout = open("easyxy.out", "w")
   main()
   sys.stdin.close()
   sys.stdout.close()

</syntaxhighlight>