Pagini recente » Cod sursa (job #3183745) | Cod sursa (job #638035) | Cod sursa (job #742727) | Cod sursa (job #1059476) | Cod sursa (job #45472)
Cod sursa(job #45472)
#include <stdio.h>
#include <fstream>
#include <deque>
using namespace std;
#define in "secventa.in"
#define out "secventa.out"
#define dim 500001
int N, K;
int A[dim];
int maxim = -1000001;
deque<int> pmin, pminp;
deque<int>::iterator it;
deque<int>::iterator it2;
int main()
{
int start, finish;
int j;
freopen(in,"r",stdin);
freopen(out,"w",stdout);
scanf("%d%d", &N, &K);
for ( int i = 1; i <= N; i++ )
scanf("%d", &A[i]);
pmin.push_back(A[1]);
pminp.push_back(1);
for ( int i = 2; i <= N; i++ )
{
if ( i <= K )
{
if ( A[i] < pmin[0] )
{
pmin.clear();
pminp.clear();
pmin.push_back(A[i]);
pminp.push_back(i);
}
else
{
j = pmin.size()-1;
while ( A[i] < pmin[j] ) pmin.pop_back(), pminp.pop_back(), j--;
pmin.push_back(A[i]);
pminp.push_back(i);
}
}
else
{
// caut daca am element de pe pozitia i-k-1;
for ( it = pminp.begin(), it2 = pmin.begin(); it != pminp.end(); it++, it2++ )
if ( *it == i-K )
{
pminp.erase(it);
pmin.erase(it2);
break;
}
if ( A[i] < pmin[0] )
{
pmin.clear();
pminp.clear();
pmin.push_back(A[i]);
pminp.push_back(i);
}
else
{
j = pmin.size()-1;
while ( A[i] < pmin[j] ) pmin.pop_back(), pminp.pop_back(), j--;
pmin.push_back(A[i]);
pminp.push_back(i);
}
}
/* for ( j = 0; j < pmin.size(); j++ )
printf("%d %d\n", pmin[j], pminp[j]);
printf("\n");*/
if ( maxim < pmin[0] )
{
if ( i <= K ) start = 1, finish = K, maxim = pmin[0];
else maxim = pmin[0], start = i-K+1, finish = i;
}
}
printf("%d %d %d", start, finish, maxim);
}