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