Cod sursa(job #2268174)

Utilizator iarinatudorTudor Iarina Maria iarinatudor Data 24 octombrie 2018 15:54:12
Problema Secventa Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <deque>

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

deque <pair <long long, int> > D;
long long n,k,mini=-30001,a,b,curr=0;
char s[6000000];
void citeste(long long &x)
{   x=0;
    int sign=1;
    if(s[curr]=='-')
    {
        sign=-1;
        curr++;

    }
    while('0'<=s[curr]&&s[curr]<= '9')
    {

        x=x*10+(s[curr]-'0');
        curr ++;

    }
    curr ++;
    x *= sign;
}
void rezolva()
{

    ios_base::sync_with_stdio(false);
    fin.getline(s,6000000);
    citeste(n);
    citeste(k);
    curr=0;
    fin.getline(s,6000000);
    long long x;
    citeste(x);

    D.push_back(make_pair(x,1));
    for (int i=2; i<k; i++)
    {
        citeste(x);

        while (!D.empty() && x < D.back().first)
            D.pop_back();
        D.push_back(make_pair(x,i));

    }

    for(int i=k; i<=n; i++)
    {
       citeste(x);

        if(!D.empty())
        {
            if(x>D.back().first)
                D.push_back(make_pair(x,i));
            else
            {
                while(!D.empty()&&D.back().first>=x)
                    D.pop_back();
                D.push_back(make_pair(x,i));
            }


        }
        else D.push_back(make_pair(x, i));
        if(i-k==D.front().second)
                D.pop_front();
        if(i>=k)
        if(D.front().first>mini)
        {
            mini=D.front().first;
            b=i;
            a=i-k+1;
        }

    }
}
int main()
{
    rezolva();
    fout<<a<<" "<<b<<" "<<mini;
    return 0;
}