Pagini recente » Cod sursa (job #1262736) | Cod sursa (job #2502628) | Cod sursa (job #1658440) | Cod sursa (job #399589) | Cod sursa (job #1197663)
/*
Keep It Simple!
*/
#include<fstream>
#include<cstring>
#include<cstdio>
using namespace std;
#define MaxN 500005
int A[MaxN],Deque[MaxN],N,K,best,beg;
char buffer[8*MaxN];
int main()
{
// ifstream f("secventa.in");
FILE *f = fopen("secventa.in","r");
ofstream g("secventa.out");
best = -(1<<30);
fscanf(f,"%d%d\n",&N,&K);
fgets(buffer,8*MaxN,f);
int size = strlen(buffer);
int sign=1,number=0;
int cnt = 0;
for(int i=0;i<size;i++)
{
if(buffer[i] == '-')
sign = -1;
else if (buffer[i] != ' ')
{
number = number*10 + buffer[i] -'0';
}
if(buffer[i] == ' ' || buffer[i] == '\n')
{
A[++cnt] = number*sign;
number = 0;
sign = 1;
}
}
int Front = 1;
int Back = 1;
Deque[1] = 1;
for(int i = 2; i < K; ++i)
{
while(Front <= Back && A[i] <= A[ Deque[Back] ]) Back--;
Deque[++Back] = i;
}
for(int i=K;i<=N;i++)
{
while(Front <= Back && A[i] <= A[Deque[Back]]) Back--;
Deque[++Back] = i;
if(Deque[Front] == i-K) Front++;
if(i>=K)
{
if(A[Deque[Front]] > best)
{
best = A[Deque[Front]];
beg = i;
}
}
}
g << beg-K+1 << " " << beg << " " << best;
g.close();
return 0;
}