Cod sursa(job #928542)

Utilizator AdrianaMAdriana Moisil AdrianaM Data 26 martie 2013 15:03:47
Problema Secventa Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <fstream>
#include <algorithm>
using namespace std;

ifstream is("secventa.in");
ofstream os("secventa.out");

int n, k;
int e[500001];
int r[500001];
int poz, nr, st, dr, m;
int p[500001];

int main()
{
    is >> n >> k;
    for ( int i = 1; i <= n; ++i )
    {
        is >> e[i];
        r[i] = e[i];
        p[e[i]] = i;
    }
    sort ( r + 1, r + n + 1 );
    poz = n - k + 2;
    nr = r[poz];
    while ( true )
    {
        --poz;
        nr = r[poz];
        m = p[nr];
        st = m;
        dr = m;
        while ( e[st] >= e[m] && st > 0 )
            --st;
        ++st;
        while ( e[dr] >= e[m] && dr <= n )
            ++dr;
        --dr;
        if ( dr - st + 1 >= k )
            break;
    }
    os << st << " " << dr << " " << nr << " ";
    is.close();
    os.close();
    return 0;
}