Pagini recente » Cod sursa (job #1649768) | Cod sursa (job #3263239) | Cod sursa (job #955145) | Cod sursa (job #2950244) | Cod sursa (job #1017787)
#include <cstdio>
#include <deque>
using namespace std;
FILE * is = fopen("secventa.in", "r");
FILE * os = fopen("secventa.out", "w");
int n, k, w[500005];
int ii, jj, bmax;
int L, R;
deque <int> q;
int main()
{
fscanf(is, "%d%d", &n, &k);
for ( int i = 1; i <= n; ++i )
fscanf(is, "%d", &w[i]);
bmax = -30001;
w[0] = -30001;
for ( int i = 1; i <= k; ++i )
{
while ( !q.empty() && w[i] < w[q.back()] )
q.pop_back();
q.push_back(i);
bmax = w[q.front()];
ii = 1;
jj = k;
}
for ( int i = k + 1; i <= n; ++i )
{
while ( !q.empty() && w[i] < w[q.back()] )
q.pop_back();
q.push_back(i);
if ( i - q.front() + 1 > k )
q.pop_front();
if ( q.front() == bmax )
{
if ( i - k + 1 < ii )
{
ii = i - k + 1;
jj = i;
}
if ( i - k + 1 == ii )
jj = min(jj, i);
}
if ( q.front() > bmax )
{
bmax = w[q.front()];
ii = i - k + 1;
jj = i;
}
}
fprintf(os, "%d %d %d", ii, jj, bmax);
fclose(is);
fclose(os);
return 0;
}
/*
while ( !q.empty() && w[i] < w[q.back()] )
q.pop_back();
while ( i - q.front() + 1 >= k )
q.pop_back();
q.push_back(i);
if ( w[q.front()] > bmax && i >= k )
{
bmax = w[q.front()];
}
*/