Cod sursa(job #2205375)

Utilizator DordeDorde Matei Dorde Data 18 mai 2018 22:05:20
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.68 kb
#include <fstream>
#include <ctype.h>
#define pb push_back
using namespace std;
char const in [] = "secventa.in";
char const out [] = "secventa.out";
int const NM = 500007 , BUFF = 1e6 + 7;
char buff [BUFF];
int v [NM] , point;
#include <deque>
deque <int> q;
int getbuff ()
{
    int nr = 0;
    bool type = 0;
    while(! isdigit (buff [point]))
    {
        if(buff [point] == '-')
            type = 1;
        ++ point;
        if(point == BUFF)
        {
            point = 0;
            fread (buff , 1 , BUFF , stdin);
        }
    }
    while(isdigit (buff [point]))
    {
        nr = nr * 10 + (buff [point] - '0');
        ++ point;
        if(point == BUFF)
        {
            point = 0;
            fread (buff , 1 , BUFF , stdin);
        }
    }
    if(type)
        nr = -nr;
    return nr;
}
int main()
{
    freopen (in , "r" , stdin);
    freopen (out , "w" , stdout);
    fread (buff , 1 , BUFF , stdin);
    int n , i , k , nr , c2 , c3 = -30100;
    n = getbuff ();
    k = getbuff ();
    for(i = 1 ; i <= n ; ++ i)
        v [i] = getbuff ();
    for(i = 1 ; i <= n ; ++ i)
    {
        if(q . empty ())
            q . pb (1);
        else
        {
            while(! q . empty () && v [i] <= v [q . back ()])
                q . pop_back ();
            if(i - q . front () == k)
                q . pop_front ();
            q . push_back (i);
            int a = q . front ();
            if(! q . empty () && i >= k && v [q . front ()] > c3)
            {
                c3 = v [q . front ()];
                c2 = i;
            }
        }
    }
    printf ("%d %d %d" , c2 - k + 1 , c2 , c3);
    return 0;
}