Cod sursa(job #49548)

Utilizator varuvasiTofan Vasile varuvasi Data 5 aprilie 2007 23:40:57
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.62 kb
#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;
}