Cod sursa(job #1816096)

Utilizator fluture.godlikeGafton Mihnea Alexandru fluture.godlike Data 26 noiembrie 2016 09:33:39
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.08 kb
/// Problema "Secventa" - InfoArena
#include <cstdio>
#include <deque>
#include <algorithm>

#define in "secventa.in"
#define out "secventa.out"
#define NMAX (500000 + 7)
#define inf (-30000 - 7)
#define DIM (100000 + 7)

using namespace std;
int n, k, tmp1, maxn = inf, p, poz;
char buff[DIM];
struct ceva
{
    int key;
    int value;
} tmp;
deque <ceva> dq;

inline void goNext()
{
    ++poz;
    if(poz == DIM)
    {
        poz = 0;
        fread(buff, 1, DIM, stdin);
    }
}
void citeste(int &nr)
{
    int semn = 1;
    nr = 0;
    while(buff[poz] < '0' || buff[poz] > '9')
    {
        if(buff[poz] == '-') semn = -1;
        goNext();
    }
    while(buff[poz] >= '0' && buff[poz] <= '9')
    {
        nr = nr * 10 + buff[poz] - '0';
        goNext();
    }
    nr = nr * semn;
}

int main()
{
     freopen(in, "r", stdin);
     freopen(out, "w", stdout);
     fread(buff, 1, DIM, stdin);
     //scanf("%d %d", &n, &k);
     citeste(n);
     citeste(k);
     for(int i = 1; i<= k-1; ++i)
     {
         //scanf("%d", &tmp1);
         citeste(tmp1);
         tmp.key = i;
         tmp.value = tmp1;
         while(!dq.empty())
         {
             ceva aux = dq.back();
             if(aux.value >= tmp.value)
             {
                 dq.pop_back();
                 continue;
             }
             break;
         }
         dq.push_back(tmp);
     }
     for(int i = k; i<=n; ++i)
     {
         //scanf("%d", &tmp1);
         citeste(tmp1);
         tmp.key = i;
         tmp.value = tmp1;
         while(!dq.empty())
         {
             ceva aux = dq.back();
             if(aux.value >= tmp.value)
             {
                 dq.pop_back();
                 continue;
             }
             break;
         }
         dq.push_back(tmp);
         tmp = dq.front();
         if(tmp.value > maxn)
         {
             maxn = tmp.value;
             p = i;
         }
         if(tmp.key <= i-k+1) dq.pop_front();
     }
     printf("%d %d %d", p-k+1, p, maxn);
     return 0;
}