Cod sursa(job #49572)

Utilizator varuvasiTofan Vasile varuvasi Data 6 aprilie 2007 00:47:39
Problema Secventa Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.04 kb
#include <stdio.h>
#include <string.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[2000000];
int start, end, answer = -INF;
char T[MaxN];
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, nr = 0, cnt = 0, len, sgn = 1;
    FILE *fin = fopen("secventa.in", "rt");
    fscanf(fin, "%d %d\n", &N, &K);
    fgets(T, 2000000, fin);
    
    i = 0, len = strlen(T);
    while (i < len)
    {
        if (T[i] == ' ')
        {
            A[++cnt] = sgn*nr, nr = 0;
            sgn = 1;
        }    
        else
            if (T[i] == '-') sgn = -1;
            else
                nr = nr * 10 + (T[i] - '0');
        i++;
    }
    A[++cnt] = nr;
         
    /*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 ", A[i]);*/
    /*fprintf(fout, "\n");
    FOR(i, 1, N)
        fprintf(fout, "%d ", min_val[i]);
    fclose(fout);*/
    /*DEBUG*/
    fclose(fout);
    return 0;
}