Cod sursa(job #1726212)

Utilizator catu_bogdan_99Catu Bogdan catu_bogdan_99 Data 7 iulie 2016 15:24:16
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <fstream>
using namespace std;

#define DIM 500005

int v[DIM];
int Q[DIM];
ifstream fin("secventa.in");
ofstream fout("secventa.out");

string buffer;
string::iterator buffer_it;

int read_int(  ) {
    while ( *buffer_it<'0' || *buffer_it>'9' ) {
        ++buffer_it;
    }
    int x = 0;
    while ( *buffer_it>='0' && *buffer_it<='9' ) {
        x = x*10+*buffer_it-'0';
        ++buffer_it;
    }
    return x;
}

int main()
{

    int n, i, j, s, p, t, d, k, ma, id, st, dr, begi, endi;
    getline(fin, buffer, (char)0);
    buffer_it = buffer.begin();

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

    ma = -(1<<23);
    dr = id = begi = endi = 0;
    st = 1;

    for( i = 1; i <= n; ++i ){

        while( st <= dr && v[Q[dr]] > v[i] ) dr--;
        dr++;
        Q[dr] = i;

        while( st <= dr && Q[st] < i - k + 1  ) st++;

        if( i >= k && v[Q[st]] > ma ){
            ma = v[Q[st]];
            begi = i - k + 1;
            endi = i;
        }

    }

    fout << begi << " " << endi << " " << ma;

    return 0;
}