Pagini recente » Cod sursa (job #337048) | Cod sursa (job #2027748) | Cod sursa (job #943517) | Cod sursa (job #2550543) | Cod sursa (job #2077233)
#include <bits/stdc++.h>
#define in "secventa.in"
#define out "secventa.out"
using namespace std;
ifstream fin(in);
ofstream fout(out);
int n,k;
int a[500003];
deque <int> q;
char s[4000003];
void Citire()
{
int i,j;
int numar,semn;
fin >> n >> k;
fin.get();
fin.getline(s,4000001);
j = 0;
for (i = 0; s[i] != 0;)
if (s[i] == ' ') i++;
else
{
semn = 1;
if (s[i] == '-')
{
semn = -1;
i++;
}
numar = 0;
while ('0' <= s[i] && s[i] <= '9')
{
numar = numar*10 + (s[i] - '0');
i++;
}
numar *= semn;
a[++j] = numar;
}
}
void Rezolvare()
{
int i,x;
int maxi;
int c1,c2;
for (i = 1; i <= k; i++)
{
x = a[i];
/// elimin toate elementele mai mari ca x
while (!q.empty() && x <= a[q.back()])
q.pop_back();
q.push_back(i);
}
maxi = a[q.front()];
c2 = q.back();
c1 = q.back()-k+1;
for (i = k+1; i <= n; i++)
{
x = a[i];
/// elimin toate elementele mai mari ca x
while (!q.empty() && x <= a[q.back()])
q.pop_back();
q.push_back(i);
/// elimin vechiul minim
if (q.front() <= i-k) q.pop_front();
/// actualizez maximul
if (a[q.front()] > maxi)
{
maxi = a[q.front()];
c2 = q.back();
c1 = q.back()-k+1;
}
}
fout << c1 << " " << c2 << " " << maxi << "\n";
}
int main()
{
Citire();
Rezolvare();
fin.close();
fout.close();
return 0;
}