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

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()