Cod sursa(job #1506609)

Utilizator mihai.alphamihai craciun mihai.alpha Data 20 octombrie 2015 20:30:46
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.67 kb
//#include <stdio.h>
//#include <stdlib.h>
//#include <math.h>
//#define MAX 500003
//int v[MAX];
//int minim = -1;
//int main(void) {
//FILE *fin, *fout;
//fin = fopen("secventa.in", "r");
//fout = fopen("secventa.out", "w");
//int n, k;
//fscanf(fin, "%d", &n);
//fscanf(fin, "%d", &k);
//int i;
//for(i = 0;i < n;i++)
//    fscanf(fin, "%d", &v[i]);
//int mini = 30003;
//    int j;
//     int ci, cf;//coordonata primului element minim
//for(i = 0;i <= n - k;i++) {
//    mini = 30003;
//    for(j = i;j <i + k;j++) {
//        if(v[j]<mini)
//            mini=v[j];
//    }
//  //  printf("%d ", mini);
//    if(mini>minim) {
//        minim = mini;
//        ci = i;//coordonata intitiala
//        cf = i + k - 1;//coordonata finala
//    }
//    if(mini == minim) {
//        if(i < ci) {
//            ci = i;
//            cf = i + k - 1;
//            minim = mini;
//        }
//        else if(i  == ci && i +k -1<cf) {
//            ci = i;
//            cf = i +k- 1;
//            minim = mini;
//        }
//    }
//}
//fprintf(fout, "%d %d %d", ci + 1, cf + 1, minim);
//fclose(fin);
//fclose(fout);
//return 0;
//}
#include <stdio.h>

typedef struct S {
    int poz, val;
} S;

int main() {
    const int NMAX = 1024;
    int x, i, fl, N, K, best = -66666, poz = 0, first, last;
    S d[50001];
    char input[1030];
    char *p;
    register char ch;

    freopen( "secventa.in", "r", stdin );
    freopen( "secventa.out", "w", stdout );

    scanf( "%d %d\n", &N, &K );
    first = last = 1;
    fgets( input, NMAX, stdin );

    p = input;
    for( i=1; i<=N; i++ ) {
        fl = 1; x = 0;
        for( ; *p != ' ' && *p != '\n'; ) {
            ch = *p;

            if( ch >= '0' && ch <= '9' )
                x = x*10 + ch - '0';
            else
                if( ch == '-' )
                    fl = -1;

            p++;
            if( p - input >= NMAX - 1 ) {
                fgets( input, NMAX, stdin );
                p = input;
            }

        }
        p++; x *= fl;

        //printf( "%d\n", x );
        //elimina elementele vechi din fata
        while( first <= last && d[first].poz <= i-K )
            first++;
        //elimina elementele prea mari din spate
        while( first <= last && d[last].val >= x )
            last--;
        //adauga x in spate
        last++;
        d[last].poz = i;
        d[last].val = x;

        //actualizeaza maxim
        if( i >= K )
            if( best < d[first].val ) {
                best = d[first].val;
                poz = i;
            }
    }
    printf( "%d %d %d\n", poz - K + 1, poz, best );
    return 0;
}