3692 - maxime

Cerinta

Se dă un șir V cu N valori naturale nenule, memorate pe poziții consecutive începând cu poziția 1. Notăm cu S 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 V a elementului de pe o anumită poziție dată P. În urma operației de eliminare elementele de pe pozițiile P + 1, P + 2, ..., N ajung pe o poziție cu 1 mai mică iar N scade cu 1.

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 rep dacă am aplica secvența S asupra șirului obținut după fiecare operație de eliminare.

Date de intrare

Fițierul maximeIN.txt conține pe prima linie un număr natural N. Pe linia a doua se află N numere naturale nenule, separate prin câte un spațiu. Pe linia următoare se află un număr M reprezentând numărul de operații de eliminare. Linia următoare conține M numere, cuprinse între 1 și N, 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 maximeOUT.txt conține pe primul rând M numere, separate prin câte un spațiu, reprezentând valoarea variabilei rep obținută aplicând secvența S după fiecare operație de eliminare. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

Restricții și precizări

• 2 ≤ N ≤ 100.000
• 1 ≤ Vi ≤ 100.000
• 1 ≤ M ≤ 100.000
• 1 ≤ poziție eliminare ≤ N

Exemplul 1:

maximeIN.txt

6
3 1 3 8 1 8
3
2 5 6

maximeOUT.txt

2 2 1

Explicație

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

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

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

Exemplul 2:

maximeIN.txt

100001
3 1 3 8 1 8
3
2 5 6

maximeOUT.txt

Datele nu corespund restrictiilor impuse

Rezolvare

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