Danciu: Pagină nouă: = 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...`


2024-06-04T07:47:22Z
Pagină nouă:  = Cerința = Se dă un vector <code>v</code> cu <code>N</code> elemente numere naturale numerotate de la <code>1</code> la <code>N</code> și <code>M</code> întrebări de forma:  * <code>x y p</code>: se afișează valoarea ce s-ar afla pe poziția <code>p</code> dacă <code>v[x...y]</code> ar fi ordonat crescător.  Să se răspundă la cele <code>M</code> întrebări.  = Date de intrare = Fișierul de intrare <code>easyxy.in</code> conține pe prima linie numerele <code>N...
New page


= Cerința =

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



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



Să se răspundă la cele <code>M</code> întrebări.



= Date de intrare =

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



= Date de ieșire =

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



= Restricții și precizări =



* <code>1 ≤ N,M ≤ 100.000</code>

* Elementele vectorului sunt <code>≤ 1.000.000.000</code>

* Pentru orice întrebare, <code>1 ≤ x ≤ p ≤ y ≤ N</code>



= Exemplu: =

<code>easyxy.in</code>

 6 3

 1 3 2 5 6 3

 1 3 2

 1 6 5

 3 5 4

<code>easyxy.out</code>

 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>

1870 - Easy xy - Revision history