Cod sursa(job #43644)

Utilizator cos_minBondane Cosmin cos_min Data 30 martie 2007 12:40:59
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <stdio.h>
#include <set>
#include <deque>
using namespace std;

#define in "secventa.in"
#define out "secventa.out"
#define dim 500001

int A[dim];

struct Functor {
    bool operator () (int i, int j)
    {
        return A[i] < A[j];
    }
};   

int Binar(int st, int dr);     

int N, K;
multiset<int, Functor> h;
multiset<int, Functor>::iterator it;

int main()
{
    freopen(in,"r",stdin);
    freopen(out,"w",stdout);
    
    scanf("%d%d", &N, &K);
    for ( int i = 1; i <= N; i++ )
        scanf("%d", &A[i]);
    
    for ( int i = 1; i <= K; i++ )
        h.insert(i);
    
    int minim;
    int inceput, sfarsit;
    
    it = h.begin();
    
    minim = A[*it];
    inceput = 1;
    sfarsit = K;
    
    int maxim = A[*it];
    
    for ( int i = K+1; i <= N; i++ )
    {
        it = h.begin();
        if ( i - K + 1 > *it ) 
        {
            h.erase( h.begin() );
        }   
        it = h.find(i-K);
        if ( *it <= N ) h.erase(it);
        h.insert(i); 
        it = h.begin();
        if ( maxim < *it ) maxim = A[*it], inceput = i-K+1, sfarsit = i;
    }    
    
    /*for ( it = h.begin(); it != h.end(); it++ )
        printf("%d\n", *it);*/
    
    printf("%d %d %d", inceput, sfarsit, maxim );
    
}