Pagini recente » Cod sursa (job #1673490) | Cod sursa (job #1441047) | Cod sursa (job #2192828) | Cod sursa (job #989652) | Cod sursa (job #1000068)
#include <iostream>
#include <fstream>
#include <climits>
#include <cstring>
using namespace std;
const int Nmax = 500005;
const int LgMax = 20;
int N, K;
int rmq[LgMax][Nmax], A[Nmax], lg[Nmax];
int maxim = -INT_MAX, 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;
string file( ( istreambuf_iterator <char>(f) ), istreambuf_iterator<char>() );
int nr = 0;
int semn = 1;
int index = 1;
int ll = file.length();
for ( int i = 1; i < ll; ++i )
{
if ( file[i] == '-' )
semn = -1;
else
if ( isdigit( file[i] ) )
nr = nr * 10 + ( file[i] - 48 );
else
{
nr *= semn;
A[ index++ ] = nr;
nr = 0;
semn = 1;
}
}
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;
}