Cod sursa(job #1661437)

Utilizator emanuel_rRamneantu Emanuel emanuel_r Data 23 martie 2016 21:10:54
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.66 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<cstdlib>
#include<deque>

using namespace std;

ofstream g("secventa.out");

deque <int> DQ;
int V[500005], S[500005];
int n, b, sol, pos;
char Buffer[100000];
int const oo = 1000000000, Buffer_Size = 100000;

void read(int & nr)
{
    bool neg;
    nr = 0;
    while((Buffer[pos] < '0' || Buffer[pos] > '9') && Buffer[pos] != '-'){
        pos++;
        if(pos == Buffer_Size){
            pos = 0;
            fread(Buffer, 1, Buffer_Size, stdin);
        }
    }
    if(Buffer[pos] == '-'){
        pos++;
        neg = 1;
        if(pos == Buffer_Size){
            pos = 0;
            fread(Buffer, 1, Buffer_Size, stdin);
        }
    }
    while(Buffer[pos] >= '0' && Buffer[pos] <= '9'){
        nr = nr*10 + Buffer[pos++] - '0';
        if(pos == Buffer_Size){
            pos = 0;
            fread(Buffer, 1, Buffer_Size, stdin);
        }
    }

    if(neg)
        nr = -nr;
}

void Read()
{
    int i;
    freopen("secventa.in", "r", stdin);
    fread(Buffer, 1, Buffer_Size, stdin);
    read(n); read(b);
    for(i=1; i<=n; i++)
        read(V[i]);
}

void Solve()
{
    int i, idx;

    sol = -oo;
    DQ.push_back(1);
    for(i=2; i<=n; i++){
        if(DQ.back() == i - b)
            DQ.pop_back();
        while(DQ.size() && V[i] <= V[DQ.front()])
           DQ.pop_front();
        DQ.push_front(i);
        S[i] = V[DQ.back()];
        if(S[i] > sol && i >= b){
            sol = S[i];
            idx = i;
        }
    }
    g<<idx - b + 1<<" "<<idx<<" "<<sol<<"\n";
}

int main()
{
    Read();
    Solve();
    return 0;
}