Cod sursa(job #615273)

Utilizator skyelHighScore skyel Data 9 octombrie 2011 02:58:02
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <stdio.h>
#include <fstream>
#include <stdlib.h>
#include <string.h>
using namespace std;
#define input "secventa.in"
#define output "secventa.out"
int array[500005], position[500005];

int main()
{
    int n,k,i,begin,end,max,maxp;
    
    char *it;
    ifstream in(input);
    ofstream out(output);
    in>>n;
    in>>k;
    for (i = 0; i < n; ++i)
    {
        in>>array[i];
    }
    begin = 1;
    end = 0;
    max = -30001;
    maxp = 0;
    for (i = 0; i < n; ++i)
    {
        while (array[i] <= array[position[end]] && end >= begin) --end;
        while (((i - position[begin]) >= k) && end >= begin) ++begin;
        
        position[++end] = i;
        if(max < array[position[begin]] && i >= (k-1)) 
        {
            max = array[position[begin]];
            maxp = i;
        }
    }
    maxp++;
    out<<maxp - k + 1<<" "<<maxp<<" "<<max;
    return 0;
}