Pagini recente » Cod sursa (job #1200504) | Clasament autumn2007-runda2 | Cod sursa (job #3243922) | Cod sursa (job #2559778) | Cod sursa (job #1097910)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <deque>
#include <cstring>
using namespace std;
ifstream fin("secventa.in");
ofstream fout("secventa.out");
const int Nmax = 5e5 + 100;
const int Smax = 2e6;
const int oo = 0x3f3f3f3f;
struct Poz_Val{
int p, v;
}E;
int N, K, V[Nmax];
deque <Poz_Val> D;
int Number(char* p)
{
int sign = 1, i = 0, nr = 0;
if(p[0] == '-') sign = -1, i++;
for(; i < strlen(p); i++)
nr = nr * 10 + p[i] - '0';
return sign * nr;
}
void Read()
{
fin.get();
char s[Smax]; int nr = 1;
fin.getline(s, Smax);
char *p = strtok(s, " ");
V[nr] = Number(p);
while(p = strtok(NULL, " "))
V[++nr] = Number(p);
}
int main()
{
fin >> N >> K;
Read();
E.v = V[1]; E.p = 1;
D.push_back(E);
for(int i = 2; i <= K; i++)
{
E.v = V[i]; E.p = i;
while(D.size() && D.back().v >= E.v)
D.pop_back();
D.push_back(E);
}
int best = D.front().v, st = 1, dr = K;
for(int i = K + 1; i <= N; i++)
{
E.v = V[i]; E.p = i;
while(D.size() && D.back().v >= E.v)
D.pop_back();
D.push_back(E);
if(D.front().p <= i - K)
D.pop_front();
if(best < D.front().v)
{
best = D.front().v;
st = i - K + 1; dr = i;
}
}
fout << st << ' ' << dr << ' ' << best;
return 0;
}