Pagini recente » Cod sursa (job #593183) | Cod sursa (job #1021636) | Cod sursa (job #2108093) | Cod sursa (job #102832) | Cod sursa (job #2227961)
#include <iostream>
#include <deque>
#include <climits>
#include <utility>
#include <fstream>
using namespace std;
ifstream in("secventa.in");
ofstream out("secventa.out");
int main()
{
long long n, k, numar;
long long inceput, sfarsit, baza_max = LONG_LONG_MIN;
deque< pair<int,int> > d; // first = valoarea, second = pozitia
in >> n >> k;
for( int i=1 ; i<=k ; i++ )
{
in >> numar;
while( d.size() && d.front().first >= numar )
d.pop_front();
d.push_front({numar,i});
}
for( int i=k+1 ; i<=n ; i++ )
{
if( d.back().first > baza_max )
{
baza_max = d.back().first;
sfarsit = d.front().second;
inceput = sfarsit - k + 1;
}
in >> numar;
while( d.size() && d.front().first >= numar )
d.pop_front();
while( d.size() && d.front().second - d.back().second + 1 > k )
d.pop_back();
d.push_front({numar,i});
}
while( d.size() && d.front().second - d.back().second + 1 > k )
{
d.pop_back();
if( d.back().first > baza_max )
{
baza_max = d.back().first;
sfarsit = d.front().second;
inceput = sfarsit - k + 1;
}
}
out << inceput << " " << sfarsit << " " << baza_max;
return 0;
}