Cod sursa(job #995231)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 8 septembrie 2013 10:49:51
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <fstream>
#include <deque>

using namespace std;

deque<int> coada;

int main()
{
    ifstream cin("secventa.in");
    ofstream cout("secventa.out");
    int n=0,k=0,i,v[500005],inc,sfar,maxim=-30005;
    cin>>n>>k;
    deque<int>::iterator it;
    for(i=0;i<n;i++)
    {
       cin>>v[i];
       while(!coada.empty())
          if((i-coada.front())>=k)
             coada.pop_front();
          else
             break;           
             
       while(!coada.empty())
          if(v[coada.back()]>=v[i])
             coada.pop_back();
          else
             break;  
       coada.push_back(i);
       
       if(i>=(k-1))
       {
           if(v[coada.front()]>maxim)
           {
              maxim=v[coada.front()];
              inc=i-k+1;
              sfar=i;                          
           }
       }
    }
    cout<<inc+1<<' '<<sfar+1<<' '<<maxim<<'\n';
    cin.close();
    cout.close();
    return 0;
}