Pagini recente » Cod sursa (job #362025) | Cod sursa (job #253945) | Cod sursa (job #3262952) | Cod sursa (job #1873467) | Cod sursa (job #2622853)
#include <fstream>
#include <climits>
using namespace std;
ifstream f("secventa.in");
ofstream g("secventa.out");
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;
static inline void Read ()
{
f.tie(nullptr);
f >> N >> Lg;
for(int i = 1; i <= N; ++i)
f >> A[i];
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)
{
if(pos_L < l || (pos_L == l && pos_R > r))
pos_L = l, pos_R = r;
}
}
}
g << pos_L << ' ' << pos_R << ' ' << ans << '\n';
return;
}
int main()
{
Read();
Precalculation();
Solve();
return 0;
}