Cod sursa(job #2347995)

Utilizator IoanStoicaStoica Ioan IoanStoica Data 19 februarie 2019 11:51:13
Problema Secventa Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <bits/stdc++.h>
#define D 500005
using namespace std;

ifstream f("secventa.in");
ofstream g("secventa.out");

struct con
{
    int val,poz;
}nr,maxim;
int n,k,i;
deque <con> a;
char s[D*6];int v[D];
void read()
{
    f>>n>>k;f.get();
    f.getline(s,D*6);
    int d=strlen(s),nr=0,semn=1,p=0;
    for(i=0;i<d;i++)
    {
        if(s[i]==' ')
            v[++p]=semn*nr,semn=1,nr=0;
        else if (s[i]=='-')
            semn=-1;
        else nr= nr*10+s[i]-'0';
    }
    v[++p]=semn*nr;
}

int main()
{
    read();
    maxim.val=INT_MIN;
    for(i=1;i<k;i++)
    {
        nr.val=v[i];nr.poz=i;
        while(!a.empty() && nr.val<=a.back().val)
            a.pop_back();
        a.push_back(nr);
    }
    for(i=k;i<=n;i++)
    {
        nr.val=v[i];nr.poz=i;
        while(!a.empty() && nr.val<=a.back().val)
            a.pop_back();
        a.push_back(nr);
        if(a.front().val>maxim.val)
        {
            maxim.val=a.front().val;
            maxim.poz=i-k+1;
        }
        if(a.front().poz<=i-k+1)
            a.pop_front();
    }
    g<<maxim.poz<<" "<<maxim.poz+k-1<<" "<<maxim.val<<"\n";
}