Pagini recente » Cod sursa (job #647772) | Cod sursa (job #311617) | Cod sursa (job #1606174) | Cod sursa (job #612487) | Cod sursa (job #429715)
Cod sursa(job #429715)
#include <fstream>
#include <deque>
#define NMAX 500100
#define mp make_pair
using namespace std;
deque<pair<int, int> > DQ;
int A[NMAX], N, best, besti, K;
void readAll(void)
{
ifstream fin("secventa.in");
fin >>N >>K;
for (int i = 1; i <= N; i++)
fin >>A[i];
fin.close();
}
void Solve(void)
{
int i;
for (i = 1; i < K; i++)
{
while (!DQ.empty() && DQ.back().first >= A[i]) DQ.pop_back();
DQ.push_back( mp(A[i], i) );
}
for (; i <= N; i++)
{
if (DQ.front().second <= i - K)
DQ.pop_front();
while (!DQ.empty() && DQ.back().first >= A[i]) DQ.pop_back();
DQ.push_back( mp(A[i], i) );
if (DQ.front().first > best)
{
best = DQ.front().first;
besti = i;
}
}
}
void writeAll(void)
{
ofstream fout("secventa.out");
fout <<besti - K + 1 <<' ' <<besti <<' ' <<best <<'\n';
fout.close();
}
int main()
{
readAll();
Solve();
writeAll();
return 0;
}