Cod sursa(job #849286)

Utilizator antonioteoZait Teodor Antonio antonioteo Data 6 ianuarie 2013 19:42:37
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <fstream>
#include <cstring>
using namespace std;
#define SIZE 5000001
int deq[SIZE];
int vect[SIZE];
char strg[SIZE * 15];
int get(int &st,int dr)
{
    int minus = 0;
    int nr = 0;
    if (strg[st] == '-')
    {
        minus = 1;
        st++;
    }
    while ('0' <= strg[st] && strg[st] <= '9' && st < dr)
    {
        nr = nr*10 + (strg[st] - '0');
        st++;
    }
    st++;
    if (minus == 0) return nr;
    else return -nr;
 
}
int main(int argc,char *argv[])
{
 
    freopen("secventa.in","r",stdin);
    freopen("secventa.out","w",stdout);
    int n;
    int k;
    int minim = -500001;
    scanf("%d%d\n",&n,&k);
    gets(strg);
    int st = 0;
    int fin = strlen (strg);
    int poz;
    int start = 0;
    int end = -1;
    for (int i=0;i<n;i++)
    {
        vect[i] = get(st,fin);
        while (end >= start && vect[i] <= vect[deq[end]])
            end--;
        end++;
        deq[end] = i;
        while (deq[end] - deq[start] >= k) start++;
        if (minim < vect[deq[start]] && i + 1 >= k)
        {
            minim = vect[deq[start]];
            poz = i;
        }
    }
    printf("%d %d %d",poz-k+2,poz +1,minim);
	return 0;
}