Pagini recente » Cod sursa (job #2129824) | Cod sursa (job #1622516) | Cod sursa (job #1306497) | Cod sursa (job #1977138) | Cod sursa (job #1865360)
#include <fstream>
#include <queue>
#include <cmath>
#include <cstdlib>
using namespace std;
ifstream fin("secventa.in");
ofstream fout("secventa.out");
struct Element
{
int val,poz;
} a[500001];
long long n, k,mini,i,capat1,capat2,m;
deque <Element> q;
int main()
{
fin >> n >> k;
for(int i = 1; i <= n; i++)
{
fin >>a[i].val;
a[i].poz=i;
}
for (int i = 1; i <= k; i++)
{
// vrem sa inseram a[i]
while (!q.empty() && q.back().val >= a[i].val)
q.pop_back();
q.push_back(a[i]);
}
int maxx = 0;
int max_dr = 0;
if (q.front().val > maxx)
{
maxx = q.front().val;
max_dr = k;
}
for (int i = k + 1; i <= n; i++)
{
// vrem sa inseram a[i]
// eliminam valorile din dreapta mai mari ca a[i]
while (!q.empty() && q.back().val >= a[i].val)
q.pop_back();
// eliminam minimum din stanga daca el nu e in secventa (i - k + 1, k)
if (!q.empty() && q.front().poz <= i - k)
q.pop_front();
// inseram elementul curent
q.push_back(a[i]);
// minimum pe secventa (i - k + 1, k) este in q.front()
if (q.front().val > maxx)
{
maxx = q.front().val;
max_dr = i;
}
}
fout << max_dr - k + 1 << ' ' << max_dr << ' ' << maxx << '\n';
return 0;
}