Cod sursa(job #1700596)

Utilizator leopop29Pop Leonard leopop29 Data 10 mai 2016 20:42:32
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <fstream>
#include <stdio.h>
#include <deque>
#define NM 500005

using namespace std;

FILE* fin=fopen("secventa.in","r");
const unsigned maxb=30000192;
char buf[maxb];
unsigned ptr=maxb;

inline int getInt(){
    int nr=0,semn=1;

    while((buf[ptr]<'0'||'9'<buf[ptr])&&buf[ptr]!='-')
        if(++ptr>=maxb)
            fread(buf,maxb,1,fin),ptr=0;
    if(buf[ptr]=='-') {
        semn=-1;
        ++ptr;
    }
    while('0'<=buf[ptr]&&buf[ptr]<='9'){
        nr=nr*10+buf[ptr]-'0';
        if(++ptr>=maxb)
            fread(buf,maxb,1,fin),ptr=0;
    }
    return nr*semn;
}

deque<int> d;
int v[NM];

int main()
{
    ifstream f("secventa.in");
    ofstream g("secventa.out");

    int n, k, mx = (1<<30)*-1, x, y;

    n = getInt();
    k = getInt();
    for(int i = 1; i <= n; ++i)
        v[i] = getInt();

    for(int p = 1; p <= n; ++p)
    {
        while(d.size() && v[d.back()] > v[p])
            d.pop_back();
        d.push_back(p);

        while(d.size() && d.front() <= p-k)
            d.pop_front();

        if(p >= k && v[d.front()] > mx)
        {
            mx = v[d.front()];
            x = p-k+1;
            y = p;
        }
    }

    g << x <<  ' ' << y << ' ' << mx;
}