Editing 3692 - maxime (section)

= 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>