Cod sursa(job #1106535)

Utilizator AeroHHorea Stefan AeroH Data 12 februarie 2014 21:29:25
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <fstream>
#include <deque>
using namespace std;
ifstream f("secventa.in");
ofstream g("secventa.out");
int i,j,k,N,M,D,a,b,X,Y,rasp=-1<<30;
deque <int> mini,maxi;
int v[500005];
int main()
{
   f>>N>>D;
   for (i=1;i<D;++i)
        {
            f>>v[i];
            if (mini.size())
            while (mini.size()&&v[mini.back()]>v[i])
                mini.pop_back();
            mini.push_back(i);
        }
   for (;i<=N;++i)
        {
            f>>v[i];
            if (mini.front()<=i-D)
                mini.pop_front();
            while (mini.size()&&v[mini.back()]>v[i])
                mini.pop_back();
            mini.push_back(i);
            if (mini.size()>=D-1&&v[mini.front()]>rasp)
                {
                    X=i-D+1;
                    Y=i;
                    rasp=v[mini.front()];
                }
        }

    g<<X<<" "<<Y<<" "<<rasp;
   return 0;

}