Cod sursa(job #1719667)

Utilizator TimoteiCopaciu Timotei Timotei Data 19 iunie 2016 22:50:53
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <iostream>
#include <fstream>
#include <stack>
#define nMax 500005

using namespace std;
int n, a[nMax], k, st[nMax], dr[nMax], mx, Dr, St;
stack <int> deq;
void read()
{
    ifstream fin("secventa.in");
    fin >> n >> k;
    for(int i = 1; i <= n; ++i){
        fin >> a[i];
        dr[i] = n;
        st[i] = 1;
    }
}
void solve()
{
    for(int i = 1; i <= n; ++i){
        while(!deq.empty() && a[i] < a[deq.top()]){
            if(dr[deq.top()] == n)dr[deq.top()] = i - 1;
            deq.pop();
        }
        deq.push(i);
    }
    while(!deq.empty())
        deq.pop();
    for(int i = n; i >= 1; --i){
        while(!deq.empty() && a[i] < a[deq.top()]){
            if(st[deq.top()] == 1)st[deq.top()] = i + 1;
            deq.pop();
        }
        deq.push(i);
    }
    for(int i = 1; i <= n; ++i){
        if(dr[i] - st[i] + 1 >= k){
            if(a[i] > mx) mx = a[i], St = st[i], Dr = dr[i];
            else if(a[i] == mx){
                if(st[i] < St) St = st[i], Dr = dr[i];
                 else if(st[i] == St && dr[i] > Dr) Dr = dr[i];
            }
        }
    }
}
void write()
{
    ofstream fout("secventa.out");
    fout << St << ' ' << Dr << ' ' << mx;
}
int main()
{
    read();
    solve();
    write();
    return 0;
}