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

Fisierul maxime.in 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 iesire

Fișierul maxime.out 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.

Restrictii si precizari

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

Exemplul 1

intrare

6

3 1 3 8 1 8

3

2 5 6

iesire

Datele introduse corespund restrictiilor impuse.

2 2 1

Exemplul 2

intrare

9

4 2 4 8 2 9

6

5 7 5

iesire

Datele de intrare nu corespund restrictiilor impuse

Rezolvare

<syntaxhighlight lang="python3" line="1"

using namespace std;

int main() {

   int N;
   cin >> N;

   vector<int> V(N + 1);
   for (int i = 1; i <= N; i++) {
       cin >> V[i];
   }

   int maxim = 0;
   int rep = 0;

   // Calculează variabila rep pentru șirul inițial
   for (int i = 1; i <= N; i++) {
       if (V[i] > maxim) {
           maxim = V[i];
       } else if (V[i] == maxim) {
           rep++;
       }
   }

   int numar_operatii;
   cin >> numar_operatii;

   for (int k = 0; k < numar_operatii; k++) {
       int P;
       cin >> P;

       // Actualizează variabilele maxim și rep după eliminarea elementului de pe poziția P
       if (V[P] == maxim) {
           rep -= 1;
           V[P] = 0; // Marchează elementul ca eliminat
           for (int i = 1; i <= N; i++) {
               if (V[i] > maxim) {
                   maxim = V[i];
               } else if (V[i] == maxim) {
                   rep++;
               }
           }
       } else {
           // Dacă elementul de pe poziția P nu este maxim, nu modificăm variabilele
           cout << rep << endl;
           continue;
       }

       cout << rep << endl;
   }

   return 0;

}

</syntaxhighlight>