Pagini recente » Cod sursa (job #2176377) | Cod sursa (job #1365950) | Cod sursa (job #2601577) | Cod sursa (job #1948798) | Cod sursa (job #45475)
Cod sursa(job #45475)
#include <stdio.h>
#include <fstream>
#include <deque>
using namespace std;
#define in "secventa.in"
#define out "secventa.out"
#define dim 500001
char linie[7*dim+dim];
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;
FILE *fin = fopen(in,"r");
freopen(out,"w",stdout);
fscanf(fin, "%d%d\n", &N, &K);
fgets(linie,7*dim+dim-1,fin);
int minus=1;
int aux=0;
j=0;
int t=0;
while ( j < strlen(linie) )
{
if ( linie[j] >= '0' && linie[j] <= '9' )
{
aux *= 10;
aux += (int)linie[j]-48;
}
else if ( linie[j] == '-' ) minus = -1;
else if ( linie[j] == ' ' || linie[j] == '\n' )
{
t+=1;
A[t] = minus*aux;
minus = 1;
aux = 0;
}
j++;
}
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] && i >= K )
{
start = i-K+1, finish = i, maxim = pmin[0];
}
}
printf("%d %d %d", start, finish, maxim);
}