Cod sursa(job #2040499)

Utilizator BourucLiviuBouruc Petru Liviu BourucLiviu Data 15 octombrie 2017 21:34:56
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.53 kb
#include <cstdio>
#include <cctype>
#include <deque>

#define BUF_SIZE 4096

using namespace std;

FILE *f = fopen("secventa.in", "r");
FILE *g = fopen("secventa.out", "w");

char buf[BUF_SIZE];
int pos = BUF_SIZE;

inline char getChar()
{
    if(pos == BUF_SIZE)
    {
        fread(buf, 1, BUF_SIZE, f);
        pos = 0;
    }
    return buf[pos++];
}

inline int read()
{
    int result = 0;
    bool sgn = 0;
    char c;
    do
    {
        c = getChar();
    } while(c != '-' && !isdigit(c));
    if(c == '-') sgn = 1;
    if(!isdigit(c)) c = getChar();
    do
    {
        result = result * 10 + (c - '0');
        c = getChar();
    } while(isdigit(c));
    return (sgn ? -result : result);
}

deque <pair <int, int> > q;

int main()
{
    int n, k, x, Max = -9999999, st, dr;
    n = read(); k = read();
    for(int i = 1; i <= k; ++i)
    {
        x = read();
        while(!q.empty() && q.back().first >= x)
            q.pop_back();
        q.push_back(make_pair(x, i));
    }
    Max = q.front().first;
    st = 1; dr = k;
    for(int i = k + 1; i <= n; ++i)
    {
        x = read();
        while(!q.empty() && q.back().first >= x)
            q.pop_back();
        q.push_back(make_pair(x, i));

        if(i - q.front().second >= k) q.pop_front();

        if(q.front().first > Max)
        {
            Max = q.front().first;
            st = i-k+1;
            dr = i;
        }
    }
    fprintf(g, "%d %d %d", st, dr, Max);
    fclose(f); fclose(g);
    return 0;
}