Pagini recente » Cod sursa (job #1624316) | Cod sursa (job #2300601) | Cod sursa (job #2105460) | Cod sursa (job #1016758) | Cod sursa (job #1048425)
#include <iostream>
#include <fstream>
#include <limits>
#include <algorithm>
using namespace std;
//int pb_014_secventa()
int main()
{
string in_file = "secventa.in";
string out_file = "secventa.out";
const int MAX_N = 1000000;
int N, K;
int x[MAX_N + 1];
ifstream ifs(in_file);
ifs >> N >> K;
//read the array
for (int i = 1; i <= N; i++) ifs >> x[i];
ifs.close();
int deq[MAX_N + 1];
deq[1] = x[1];
int Fd = 1, Ld = 1;
int id_mm = 1, max_min = numeric_limits<int>::min();
for (int i = 2; i <= N; i++)
{
//insert one element in the proper location in the deq
while (Ld - Fd >= 0 && x[i] < deq[Ld]) Ld--;
deq[++Ld] = x[i];
if (i >= K)
{
int cmin = deq[Fd];
if (cmin > max_min) { max_min = cmin; id_mm = i; }
if (x[i - K + 1] == deq[Fd]) Fd++; //pop the first element
}
}
ofstream ofs(out_file);
ofs << id_mm - K + 1 << " " << id_mm << " " << max_min;
return 0;
}