Secvmax

Fiona are o secventa de N numere naturale. Ea se intreaba din cand in cand pentru un anumit numar Q care este cea mai lunga subsecventa care are toate numerele mai mici sau egale cu Q. Ajutati-o pe Fiona sa isi rapunda la toate intrebarile.

Date de intrare

Fişierul de intrare secvmax.in contine pe prima linie doua numere separate printr-un spatiu N si M ce reprezinta lungimea secventei initiale si numarul de intrebari ale Fionei. Urmatoarea linie contine cele N numere naturale separate printr-un spatiu fiecare. Urmatoarele M linii contin fiecare cate un numar Q reprezentand intrebarile Fionei.

Date de ieşire

Fişierul de iesire secvmax.out va contine M linii reprezentand raspunsurile la intrebarile Fionei. Mai exact linia i contine raspunsul la a i-a intrebare si anume lungimea celei mai lungi subsecvente care are toate numerele mai mici sau egale cu Qi.

Restricţii

  • 1 ≤ N, M ≤ 105
  • Toate numerele din fisierul de intrare vor fi cuprinse intre 0 si 109
#include <fstream>
	
#include <stack>
	
#include <algorithm>
	
 
	
using namespace std;
	
 
	
ifstream f("secvmax.in");
	
ofstream g("secvmax.out");
	
 
	
struct pereche
	
{
	
    int x, y;
	
};
	
 
	
int n, m, a[101000], i, lung, secvmax[101000], q, sol;
	
int st, dr, mij;
	
int uemmst[101000];
	
int uemmdr[101000];
	
stack<pereche> stk;
	
pereche secv[101000];
	
 
	
bool perechecomp(pereche a, pereche b)
	
{
	
    if (a.x < b.x) {
	
        return true;
	
    }
	
    else if (a.x == b.x) {
	
        if (a.y < b.y)
	
            return true;
	
        return false;
	
    }
	
    return false;
	
}
	
 
	
int main()
	
{
	
    f >> n >> m;
	
 
	
    for (i = 1; i <= n; i++) {
	
        f >> a[i];
	
        while (!stk.empty() && stk.top().y < a[i]) {
	
            uemmdr[stk.top().x] = i;
	
            stk.pop();
	
        }
	
        stk.push({i, a[i]});
	
    }
	
    while (!stk.empty()) {
	
        uemmdr[stk.top().x] = n + 1;
	
        stk.pop();
	
    }
	
 
	
    for (i = n; i >= 1; i--) {
	
        while (!stk.empty() && stk.top().y < a[i]) {
	
            uemmst[stk.top().x] = i;
	
            stk.pop();
	
        }
	
        stk.push({i, a[i]});
	
    }
	
    while (!stk.empty()) {
	
        uemmst[stk.top().x] = 0;
	
        stk.pop();
	
    }
	
 
	
    for (i = 1; i <= n; i++) {
	
        lung = uemmdr[i] - uemmst[i] - 1;
	
        secv[i] = {a[i], lung};
	
    }
	
 
	
    sort(secv + 1, secv + n + 1, perechecomp);
	
 
	
    secvmax[1] = secv[1].y;
	
    for (i = 2; i <= n; i++)
	
        secvmax[i] = max(secvmax[i-1], secv[i].y);
	
 
	
    for (i = 1; i <= m; i++) {
	
        f >> q;
	
        st = 1;
	
        dr = n;
	
        sol = -1;
	
        while (st <= dr) {
	
            mij = (st + dr) / 2;
	
            if (secv[mij].x <= q) {
	
                sol = mij;
	
                st = mij + 1;
	
            }
	
            else
	
                dr = mij - 1;
	
        }
	
        if (sol == -1)
	
            g << 0 << '\n';
	
        else
	
            g << secvmax[sol] << '\n';
	
    }
	
    f.close();
	
    g.close();
	
    return 0;
	
}
%d bloggers like this: