Pagini recente » Cod sursa (job #2882176) | Monitorul de evaluare | Cod sursa (job #2158178) | Cod sursa (job #485628) | Cod sursa (job #1000064)
#include <iostream>
#include <fstream>
using namespace std;
const int Nmax = 500005;
const int LgMax = 20;
int N, K;
int rmq[LgMax][Nmax], A[Nmax], lg[Nmax];
int maxim, stanga, dreapta;
void RMQ()
{
for ( int i = 1; i <= N; ++i )
rmq[0][i] = A[i];
for ( int i = 1; ( 1 << i ) <= N; ++i )
for ( int j = 1; j + ( 1 << i ) - 1 <= N; ++j )
{
int p = 1 << ( i - 1 );
rmq[i][j] = min( rmq[i - 1][j], rmq[i - 1][j + p] );
}
for ( int i = 2; i <= N; ++i )
lg[i] = lg[i / 2] + 1;
}
int main()
{
ifstream f("secventa.in");
ofstream g("secventa.out");
f >> N >> K;
for ( int i = 1; i <= N; ++i )
f >> A[i];
RMQ();
int l = 0, r = K - 1;
while ( r < N )
{
l++;
r++;
int diff = r - l + 1;
int k = lg[diff];
int p = 1 << k;
int sh = diff - p;
int m = min( rmq[k][l], rmq[k][l + sh] );
if ( m > maxim )
{
maxim = m;
stanga = l;
dreapta = r;
}
}
g << stanga << " " << dreapta << " " << maxim << "\n";
return 0;
}