Pagini recente » Cod sursa (job #3363160) | Cod sursa (job #3363186) | Cod sursa (job #3363144) | Cod sursa (job #3363206) | Cod sursa (job #3363193)
#include <bits/stdc++.h>
const int N = 500001;
using namespace std;
ifstream in ("secventa.in");
ofstream out("secventa.out");
deque <int> d;
int n, a[N], stk[N], st[N], dr[N], cnt, x, k = 1, k1, ind1, ind2, mx;
int main()
{
in >> n >> k1;
for (int i = 1; i <= n; i++)
{
in >> a[i];
}
a[0] = INT_MIN;
a[n + 1] = INT_MIN;
stk[0] = 0;
for (int i = 1; i <= n; i++)
{
//cout << "OK";
while (a[stk[k - 1]] >= a[i])
{
stk[k - 1] = 0;
k--;
}
st[i] = stk[k - 1];
if (stk[k - 1] == 0)
st[i] = i;
stk[k] = i;
k++;
}
k = 1;
stk[0] = n + 1;
a[0] = INT_MIN;
//cout << "OK";
for (int i = n; i > 0; i--)
{
while (a[stk[k - 1]] >= a[i])
{
stk[k - 1] = 0;
k--;
}
dr[i] = stk[k - 1];
if (stk[k - 1] == n + 1)
dr[i] = i;
stk[k] = i;
k++;
}
int mx = INT_MIN;
for (int i = 1; i <= n; i++)
{
if (mx < a[i] && dr[i] - 1 - st[i] >= k1)
{
ind1 = st[i] + 1;
ind2 = dr[i] - 1;
mx = a[i];
//cout << mx << endl;
}
}
//cout << dr[n - 3] << " " << st[n - 3] << endl;
out << ind1 << " " << ind2 << " " << mx;
return 0;
}