Cod sursa(job #2306462)

Utilizator UnseenMarksmanDavid Catalin UnseenMarksman Data 22 decembrie 2018 13:22:51
Problema Secventa Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <iostream>
#include <fstream>
#include <deque>
#include <cstring>
#define maxn 500000
using namespace std;

ifstream fin("secventa.in");
ofstream fout("secventa.out");

int n, k, maxim=-30001, v[maxn+2], pos;
int posi, posj;
string s;
deque<int>dq;

int main()
{
    fin>>n>>k;
    fin.get();
    getline(fin,s);
    for(int i=0; i<s.size(); i++)
    {
        int t=0;
        if(s[i]=='-')
        {
            i++;
            while(s[i]>='0'&&s[i]<='9')
            {
                t=t*10+('0'-s[i]);
                i++;
            }
            v[++pos]=t;
        }
        else if('0'<=s[i]&&s[i]<='9')
        {
            while('0'<=s[i]&&s[i]<='9')
            {
                t=t*10+(s[i]-'0');
                i++;
            }
            v[++pos]=t;
        }
    }
    for(int i=1; i<=n; i++)
    {
        while(!dq.empty()&&v[i]<=v[dq.back()])
        {
            dq.pop_back();
        }
        dq.push_back(i);
        if(i-k==dq.front())
        {
            dq.pop_front();
        }
        if(i>=k&&maxim<v[dq.front()])
        {
            maxim=v[dq.front()];
            posi=i;
            posj=i-k+1;
        }
    }
    fout<<posj<<' '<<posi<<' '<<maxim<<'\n';
    return 0;
}