Cod sursa(job #937461)

Utilizator ericptsStavarache Petru Eric ericpts Data 10 aprilie 2013 13:47:57
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <deque>
#include <cstdio>

using namespace std;

#define push push_back
#define rm_front() while(!Q.empty() && Q.front() < i - k + 1)Q.pop_front()
#define rm_back() while(!Q.empty() && v[Q.back()] >= v[i])Q.pop_back()

const int maxn = 500100;
short v[maxn];
int n,k;
deque<int> Q;
int best = -(1<<30),st,fin;
char * buffer;

void prep(){
    freopen("secventa.in","r",stdin);
    freopen("secventa.out","w",stdout);
    int len;
    fseek(stdin,0,SEEK_END);
    len = ftell(stdin);
    buffer = new char[len];
    rewind(stdin);
    fread(buffer,1,len,stdin);
}

template<class T>
void read(T & x){
    x = 0;
    int semn = 1;
    while( (*buffer == ' ' || *buffer == '\n')&& *buffer)
        ++buffer;
    if(*buffer == '-'){
        semn = -1;
        ++buffer;
    }
    while(*buffer >= '0' && *buffer <= '9'){
        x = x * 10 + *buffer - '0';
        ++buffer;
    }
    x *= semn;
}

int main()
{
    prep();

    read(n);
    read(k);

    int i;for(i = 1 ; i <= n ; ++ i){

        read(v[i]);

        rm_front();
        rm_back();

        Q.push(i);

        if(v[Q.front()] > best && i >= k){
            fin = i;
            st = min(i-k+1,Q.front());
            best = v[Q.front()];
        }
    }
    printf("%d %d %d\n",st,fin,best);
    return 0;
}