La proba de sărituri cu schiurile din cadrul jocurilor olimpice de iarnă participă N concurenți, numerotați cu numere de la 1 la N.

Regulile de desfășurare a probei sunt următoarele:

concurenții evoluează pe rând, în ordine de la 1 la N;
fiecare concurent va efectua o singură săritură;
după efectuarea săriturii fiecare concurent primește un anumit punctaj;
pe tot parcursul concursului, comisia de arbitri are obligația să alcătuiască o listă cu punctajele obținute de concurenți, în ordinea evoluției lor;
evoluția unui concurent durează exact un minut;
nu se face pauză între evoluțiile a doi concurenți care au numere de ordine consecutive;
afișarea punctajului nu necesită timp suplimentar după efectuarea săriturii;
proba se încheie la un minut după evoluția ultimului concurent.

Pe tot parcursul concursului se ține în mod neoficial și un clasament parțial, pe baza rezultatelor obținute de concurenții care au evoluat până în acel moment. Asta pentru că șeful comisiei de arbitri are o curiozitate aparte și pune K întrebări sub forma următoare: Câte minute s-a ocupat primul loc din clasament cu un punctaj egal cu X puncte? Dacă nici un concurent nu s-a clasat pe primul loc cu X puncte atunci primește ca răspuns valoarea 0.

Cerința

Scrieți un program care determină răspunsul pentru fiecare dintre cele K întrebări puse de șeful comisiei de arbitri.

Date de intrare

Fișierul de intrare schi.in conține pe prima linie un număr natural, N reprezentând numărul de concurenți. Pe a doua linie a fișierului sunt scrise cele N numere naturale separate prin câte un spațiu, reprezentând punctajele obținute de fiecare dintre cei N concurenți, în ordinea în care aceștia au evoluat. Pe a treia linie a fișierului este scris numărul natural K ce reprezintă numărul de întrebări puse de șef. Pe a patra linie a fișierului sunt scrise K numere naturale separate prin câte un spațiu, reprezentând valorile X ale punctajelor alese de șeful comisiei de arbitri.

Date de ieșire

Fișierul de ieșire schi.out va conține pe prima linie K numere, separate prin câte un spațiu, reprezentând, în ordine, răspunsurile la cele K întrebări.

Restricții și precizări

1 ≤ N ≤ 100 000
1 ≤ K ≤ 100 000
0 ≤ punctajele obținute de concurenți ≤ 1 000 000 000
0 ≤ valorile X alese de șeful arbitrilor ≤ 1 000 000 000

Exemplu

schi.in

10
1 6 5 3 6 8 8 6 1 9
6
5 1 6 8 2 9

schi.out

0 1 4 4 0 1

Explicație

Cu punctajul 5 nu s-a ocupat niciodată locul 1, cu punctajul 1 s-a ocupat primul loc un singur minut, cu punctajele 6 și 8 s-a ocupat locul 1 câte 4 minute. Cu punctajul 2 nu s-a ocupat locul 1. El nici nu a fost obținut de vreun concurent. Cu punctajul 9 s-a ocupat locul 1 un minut.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Schi:

#include <fstream>
#define DIM 100010
using namespace std;

int v[DIM];
int n, i, T, st, dr, x, q, maxim;

int cautMinim(int x);
int cautMaxim(int x);

int main(){
    ifstream fin("schi.in");
    ofstream fout("schi.out");
    fin>>n;
    maxim = -1;
    for (i=1;i<=n;i++) {
        fin>>x;
        if (x > maxim)
            maxim = x;
        v[i] = maxim;
    }
    fin>>q;
    for (i=1;i<=q;i++) {
        fin>>x;
        st = cautMinim(x);
        if (st == -1)
            fout<<"0 ";
        else {
            dr = cautMaxim(x);
            fout<<dr-st+1<<" ";
        }
    }

    return 0;
}


int cautMinim(int x) {
    int p = 1, u = n, mid;
    while (p<=u) {
        mid = (p+u)/2;
        if (x<=v[mid]) {
            u = mid-1;
        } else {
            p = mid+1;
        }
    }
    if (v[p] == x)
        return p;
    else
        return -1;

}

int cautMaxim(int x) {
    int p = 1, u = n, mid;
    while (p<=u) {
        mid = (p+u)/2;
        if (x>=v[mid]) {
            p = mid+1;
        } else {
            u = mid-1;
        }
    }
    if (v[u] == x)
        return u;
    else
        return -1;

}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #1048 Schi

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1048 Schi de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #1048 Schi