Pagini recente » Cod sursa (job #1716964) | Cod sursa (job #457360) | Cod sursa (job #488583) | Cod sursa (job #1468764) | Cod sursa (job #2622856)
#include <iostream>
#include <cstdio>
#include <climits>
using namespace std;
const int NMAX = 5e5 + 5;
int N, A[NMAX], Lg;
int Stiva[NMAX], K;
int Left[NMAX], Right[NMAX];
int ans = INT_MIN, pos_L, pos_R;
namespace InParser
{
static const int BSIZE = (1 << 16);
int pos = BSIZE - 1;
char buff[BSIZE];
static inline char Char ()
{
++pos;
if(pos == BSIZE)
{
pos = 0;
int n = fread(buff, 1, BSIZE, stdin);
if(n != BSIZE)
for(int i = n; i < BSIZE; ++i)
buff[i] = 0;
}
return buff[pos];
}
static inline int Int ()
{
int r = 0, sign = 1;
for( ; ; )
{
char Ch = Char();
if(Ch == '-')
{
sign = -1;
break;
}
if(Ch >= '0' && Ch <= '9')
{
r = (int)(Ch - '0');
break;
}
}
for( ; ; )
{
char Ch = Char();
if(Ch >= '0' && Ch <= '9')
r = r * 10 + (int)(Ch - '0');
else
break;
}
return (r * sign);
}
};
static inline void Read ()
{
ios_base :: sync_with_stdio(false);
cin.tie(nullptr);
freopen("secventa.in", "r", stdin);
freopen("secventa.out", "w", stdout);
N = InParser :: Int(), Lg = InParser :: Int();
for(int i = 1; i <= N; ++i)
A[i] = InParser :: Int();
return;
}
static inline void Precalculation ()
{
for(int i = 1; i <= N; ++i)
{
while(K && A[i] < A[Stiva[K]])
{
Right[Stiva[K]] = i;
--K;
}
Stiva[++K] = i;
}
for(int i = 1; i <= K; ++i)
Right[Stiva[i]] = (N + 1);
K = 0;
for(int i = N; i >= 1; --i)
{
while(K && A[i] < A[Stiva[K]])
{
Left[Stiva[K]] = i;
--K;
}
Stiva[++K] = i;
}
return;
}
static inline void Solve ()
{
for(int i = 1; i <= N; ++i)
{
int l = Left[i] + 1, r = Right[i] - 1;
int k = r - l + 1;
if(k >= Lg)
{
r = l + Lg - 1;
if(A[i] > ans)
{
ans = A[i];
pos_L = l, pos_R = r;
continue;
}
if(A[i] < ans)
continue;
if(pos_L < l || (pos_L == l && r < pos_R))
pos_L = l, pos_R = r;
}
}
printf("%d %d %d", pos_L, pos_R, ans);
return;
}
int main()
{
Read();
Precalculation();
Solve();
return 0;
}