View source for 3692 - maxime

== Cerinta ==

Se dă un șir <code>V</code> cu <code>N</code> valori naturale nenule, memorate pe poziții consecutive începând cu poziția <code>1</code>. Notăm cu <code>S</code> următoarea secvență de cod aplicată asupra sa:

(C/C++)
 maxim = 0;
 rep = 0;
 for(i = 1; i <= N; i++)
 	if(V[i] > maxim)
 		maxim = V[i];
 	else
 		if(V[i] == maxim)
 			rep++;
Considerăm operația de eliminare din <code>V</code> a elementului de pe o anumită poziție dată <code>P</code>. În urma operației de eliminare elementele de pe pozițiile <code>P + 1, P + 2, ..., N</code> ajung pe o poziție cu <code>1</code> mai mică iar <code>N</code> scade cu <code>1</code>.

Dându-se mai multe operații de eliminare(independente una de alta, adică fiecare se aplică asupra șirului inițial, nu după operația anterioară), să se determine valoarea variabilei <code>rep</code> dacă am aplica secvența <code>S</code> asupra șirului obținut după fiecare operație de eliminare.

= Date de intrare =
Fițierul <code>maximeIN.txt</code> conține pe prima linie un număr natural <code>N</code>. Pe linia a doua se află <code>N</code> numere naturale nenule, separate prin câte un spațiu. Pe linia următoare se află un număr <code>M</code> reprezentând numărul de operații de eliminare. Linia următoare conține <code>M</code> numere, cuprinse între <code>1</code> și <code>N</code>, ce reprezină poziția din șir a elementului la care se realizează eliminarea curentă. Numerele de pe această linie sunt separate prin câte un spațiu.

= Date de ieșire =
Fișierul <code>maximeOUT.txt</code> conține pe primul rând <code>M</code> numere, separate prin câte un spațiu, reprezentând valoarea variabilei <code>rep</code> obținută aplicând secvența <code>S</code> după fiecare operație de eliminare.

= Restricții și precizări =

* <code>2 ≤ N ≤ 100.000</code>
* <code>1 ≤ Vi</code> <code>≤ 100.000</code>
* <code>1 ≤ M ≤ 100.000</code>
* <code>1 ≤ poziție eliminare ≤ N</code>

= Exemplul 1: =
<code>maximeIN.txt</code>
 6
 3 1 3 8 1 8
 3
 2 5 6
<code>maximeOUT.txt</code>
 2 2 1

=== Explicație ===
Aplicând prima operație de eliminare, șirul devine: <code>N = 5</code> și <code>V = 3 3 8 1 8</code>, valoarea <code>rep</code> devine <code>2</code>.

Aplicând a doua operație de eliminare, șirul devine: <code>N = 5</code> și <code>V = 3 1 3 8 8</code>, valoarea <code>rep</code> devine <code>2</code>.

Aplicând a treia operație de eliminare, șirul devine: <code>N = 5</code> și <code>V = 3 1 3 8 1</code>, valoarea <code>rep</code> devine <code>1</code>.

== Exemplul 2: ==
<code>maximeIN.txt</code>
 100001
 3 1 3 8 1 8
 3
 2 5 6
<code>maximeOUT.txt</code>
 Datele nu corespund restrictiilor impuse

== Rezolvare == 

<syntaxhighlight lang="python3" line="1" def="" calculeaza_rep(v):="" maxim="0" rep="0" for="" val="" in="" v:="" if=""> NMAX = 100005

def verifica_restricții(n, a, m, queries):
    """Verifică dacă datele de intrare respectă restricțiile impuse."""
    if not (2 <= n <= 100000):
        return False
    if any(v < 1 or v > 100000 for v in a):
        return False
    if not (1 <= m <= 100000):
        return False
    if any(p < 1 or p > n for p in queries):
        return False
    return True

def main():
    with open("maximeIN.txt", "r") as fin, open("maximeOUT.txt", "w") as fout:
        n = int(fin.readline().strip())
        a = list(map(int, fin.readline().strip().split()))
        m = int(fin.readline().strip())
        queries = list(map(int, fin.readline().strip().split()))

        if not verifica_restricții(n, a, m, queries):
            fout.write("Datele nu corespund restrictiilor impuse")
            return

        premaxim = maxim = -1
        pozpremaxim = pozmaxim = -1
        rep = varf = 0
        CNT = [0] * (NMAX + 2)
        PZ = [0] * (NMAX + 2)
        st = [0] * (NMAX + 2)
        DR = [0] * (NMAX + 2)
        OK = [0] * (NMAX + 2)

        for i in range(1, n + 1):
            if a[i-1] > maxim:
                premaxim, pozpremaxim = maxim, pozmaxim
                maxim, pozmaxim = a[i-1], i
                if pozpremaxim >= 1:
                    PZ[pozpremaxim] = i
                PZ[pozmaxim] = -1
                CNT[i] = 1
            else:
                while varf > 0 and a[i-1] > a[st[varf]-1]:
                    varf -= 1
                if pozmaxim >= 1 and PZ[pozmaxim] == 0 and a[i-1] >= premaxim:
                    PZ[pozmaxim] = i
                    if a[i-1] == premaxim:
                        OK[pozmaxim] = 1
                if a[i-1] == maxim:
                    CNT[i] = 2
                    rep += 1

            st[varf + 1] = i
            varf += 1

        for i in range(n, 0, -1):
            while varf > 0 and a[i-1] > a[st[varf]-1]:
                varf -= 1
            DR[i] = 1 + DR[st[varf]] if a[i-1] == a[st[varf]-1] else DR[st[varf]]
            st[varf + 1] = i
            varf += 1

        for p in queries:
            if CNT[p] == 0:
                fout.write(f"{rep} ")
            elif CNT[p] == 2:
                fout.write(f"{rep - 1} ")
            elif CNT[p] == 1:
                if OK[p]:
                    fout.write(f"{1 + rep - DR[p] + DR[PZ[p]]} ")
                else:
                    fout.write(f"{rep - DR[p] + DR[PZ[p]]} ")

        fout.write("\n")  # Scriem un newline la sfârșit pentru a încheia output-ul

if __name__ == "__main__":
    main()

</syntaxhighlight>