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.

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

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