Pagini recente » Clasament utcn-2022 | Cod sursa (job #681337) | Cod sursa (job #2835074) | Cod sursa (job #1062153) | Cod sursa (job #604725)
Cod sursa(job #604725)
#include <stdio.h>
#include <deque>
#include <fstream>
#define N 500005
using namespace std;
int n,k,a[N];
deque<int> q;
ifstream fin("secventa.in");
int main()
{
freopen("secventa.out","w",stdout);
fin >> n >> k;
for (int i = 0; i< n ; ++i)
fin >> a[i];
for (int i = 0 ; i < k ; ++i)
{
while (!q.empty() && a[i] <= a[q.front()] )
q.pop_front();
q.push_front(i);
}
int best = a[q.back()];
int start = 1;
int end = k;
for (int i = k ; i < n ; ++i)
{
while (!q.empty() && q.back() < (i - k + 1))
q.pop_back();
while (!q.empty() && a[i] <= a[q.front()])
q.pop_front();
q.push_front(i);
if (a[q.back()] > best)
{
best = a[q.back()];
start = i - k + 2;
end = i + 1;
}
}
printf("%d %d %d\n",start,end,best);
return 0;
}