Cod sursa(job #49564)

Utilizator varuvasiTofan Vasile varuvasi Data 6 aprilie 2007 00:37:15
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.6 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 (!varf) 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 >= K && answer < A[stmin[baza]])
		answer = A[stmin[baza]], start = i - K + 1 , 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", 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*/
    fclose(fout);
    return 0;
}