Pagini recente » Cod sursa (job #2842201) | Cod sursa (job #738800) | Cod sursa (job #2168162) | Cod sursa (job #2677124) | Cod sursa (job #49548)
Cod sursa(job #49548)
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#define FOR(i, a, b) for (i = (a); i <= (b); i++)
#define REP(i, b) for (i = 1; i <= (b); i++)
#define FORD(i, a, b) for (i = (a); i >= (b); i--)
#define MaxN 500001
#define INF 30002
int N, K;
int stmin[MaxN], baza, varf;
int min_val[MaxN];
int A[MaxN];
int start, end, answer = -INF;
void Istmin(int i)
{
/*0. daca stiva este goala*/
if (!stmin[baza]) stmin[++varf] = i;
else
{
/*1. daca elementul e mai mare decat capul stive*/
if (A[i] > A[stmin[varf]])
stmin[++varf] = i;
else
{/*2. elementul e mai mic decat capul stivei*/
while (varf >= baza && A[i] < A[stmin[varf]]) varf--;
stmin[++varf] = i;
}
/*3. diferenta dintre poz elementului curent si pozitia elem de la baza stivei > K*/
while ( i - stmin[baza] + 1 > K) baza++;
}
if ( i - stmin[baza] + 1 == K && answer < A[stmin[baza]])
answer = A[stmin[baza]], start = stmin[baza], end = i;
}
int main()
{
int i, j;
FILE *fin = fopen("secventa.in", "rt");
fscanf(fin, "%d %d", &N, &K);
FOR(i, 1, N)
fscanf(fin, "%d", &A[i]);
fclose(fin);
FOR(i, 1, N) min_val[i] = INF;
/*begin straight-forward min deque*/
baza = 1, varf = 0;
FOR(i, 1, N) Istmin(i);
/*end straight-forward min deque*/
FILE *fout = fopen("secventa.out", "wt");
fprintf(fout, "%d %d %d\n", start, end, answer);
/*DEBUG*/
/*FOR(i, 1, N)
fprintf(fout, "%d ", max_val[i]);
fprintf(fout, "\n");
FOR(i, 1, N)
fprintf(fout, "%d ", min_val[i]);
fclose(fout);*/
/*DEBUG*/
return 0;
}