3229 - The Grade

Enunt

Aleku Turcul este la ora de matematica. În timp ce el încearcă să-și dea seama dacă 1+1=2, profesorul scrie pe tablă o problemă ceva mai complicată. Se dau Q queryuri și o listă S cu P elemente egale cu 0. Notăm cu A un șir, care inițial este vid. Queryurile pot fi de forma: - 0 x (inserează valoarea x în A) - 1 x (șterge valoarea x din A; se garantează că există cel puțin o valoare de x în A) Se garantează că A nu va fi niciodată vid după vreun query. După fiecare query profesorul îi pune lui Aleku următoarea întrebare: oare pot așeza în lista S toate numerele din A (nu neapărat în ordinea în care se află în A) astfel încât:

elementele din A se vor așeza în S pe poziții distincte, restul pozițiilor din S fiind ocupate de elemente cu valoarea 0 fie S[i] un element nenul din S și S[j] cel mai apropiat element nenul care se află în stânga lui S[i] în S. Atunci următoarea condiție trebuie respectată: i - j ≥ S[i] fie f poziția celui mai din stânga element nenul din S. Atunci f ≥ S[f]. Dacă răspunsul la întrebarea profesorului este da, atunci să se spună și câte configurații diferite se pot obține. Deoarece răspunsul la întrebare poate fi foarte mare, acesta se va afișa modulo 1.000.000.007. Dacă răspunsul este nu, se va afișa -1.

Cerinţa

Ajutați-l pe Aleku sa răspundă corect la întrebările profesorului pentru ca sa obțină nota 10. Media lui depinde de aceasta! == Date dePrima linie se vor citi de la tastatură două numere naturale Q și P. Pe următoarele Q linii se află Q query-uri sub forma descrisă în enunț.

Date de ieșire

Se vor afișa pe ecran răspunsurile la cele Q query-uri, câte unul pe linie.

Restricţii şi precizări

• 1 ≤ Q, P ≤ 100.000
• Răspunsurile se vor afișa modulo 1.000.000.007.
• Numerele ce vor fi adăugate/șterse la un query sunt mai mici sau egale decât 1.000.000.
• ATENȚIE! În cazul în care răspunsul unui query este NU, se va afișa -1.
• Aleku nu este turc. Turcul este numele lui. El este de fapt căpitan.

Exemplul 1

Intrare

 9 8
 0 3
 0 3
 0 2
 1 2
 0 1
 0 1
 0 1
 1 3
 1 1

Ieșire

 6
 6
 3
 6
 12
 6
 -1
 60
 60

Rezolvare

<syntaxhighlight lang="python" line> MOD = 1000000007

def get_configurations(A):

   config_count = 1
   last_nonzero_pos = -1
   for i in range(len(A)):
       if A[i] != 0:
           if i - last_nonzero_pos < A[i]:
               return 0
           last_nonzero_pos = i
       if last_nonzero_pos + 1 < A[0]:
           return 0
       if last_nonzero_pos == A[0] - 1:
           config_count *= 2
           config_count %= MOD
   return config_count

def solve(Q, P, queries):

   A = []
   configurations = []
   result = []

   for query in queries:
       if query[0] == 0:
           A.append(query[1])
       else:
           A.remove(query[1])
       configurations.append(get_configurations(A))
   
   for config in configurations:
       if config == 0:
           result.append(-1)
       else:
           result.append(config)
   
   return result

def main():

   Q, P = map(int, input().split())
   queries = [list(map(int, input().split())) for _ in range(Q)]

   result = solve(Q, P, queries)

   for res in result:
       print(res)

if __name__ == "__main__":

   main()

</syntaxhighlight>