Cod sursa(job #2044433)

Utilizator sebi110Ciobanu Sebastian sebi110 Data 21 octombrie 2017 09:59:00
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <fstream>
#include <queue>
using namespace std;
ifstream fin("secventa.in");
ofstream fout("secventa.out");
struct data{
    int ind,x;
};
int a[500001];
deque <data> vect;
int main()
{
    data aux;
    int n,k,i,maxim,incep;
    freopen("secventa.in","r",stdin);
    freopen("secventa.out","w",stdout);
    scanf("%d %d", &n, &k);
    for(i=1;i<=n;i++)
        scanf("%d", &a[i]);
    for(i=1;i<=k;i++)
    {
        while(!vect.empty() && vect.back().x>a[i])
            vect.pop_back();
        aux.ind=i;aux.x=a[i];
        vect.push_back(aux);
    }
    maxim=vect.front().x;
    incep=1;
    for(i=k+1;i<=n;i++)
    {
        while(!vect.empty() && vect.front().ind<=i-k)
            vect.pop_front();
        while(!vect.empty() && vect.back().x>a[i])
            vect.pop_back();
        aux.ind=i;aux.x=a[i];
        vect.push_back(aux);
        if(maxim<vect.front().x)
        {
            maxim=vect.front().x;
            incep=i-k+1;
        }
    }
    fout<<incep<<' '<<incep+k-1<<' '<<maxim<<'\n';
    return 0;
}