Cod sursa(job #995236)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 8 septembrie 2013 11:59:15
Problema Secventa Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <fstream>
#include <cstring>
#include <deque>

using namespace std;

deque<int> coada;

    char sir[4000005];
int main()
{
    ifstream cin("secventa.in");
    ofstream cout("secventa.out");
    int n=0,k=0,lung,i,poz=0,v[500005],inc=-1,sfar=-1,maxim=-30005;
    cin>>n>>k;
    cin.get();
    cin.get(sir,4000005);
    lung=strlen(sir);
    bool semn;
    int nr;
    for(i=0;i<lung;i++)
    {
       if(sir[i]==' ')
       {
           v[poz++]=(((semn==1)*-2)+1)*nr;
           nr=0;
           semn=0;            
       }
       else if(sir[i]=='-')
          semn=1;
       else
       {
          nr*=10;
          nr+=(sir[i]-'0');    
       }
    }
           v[poz++]=(((semn==1)*-2)+1)*nr;
           nr=0;
           semn=0;         
    
    for(i=0;i<n;i++)
    {
                  //  cout<<"v["<<i<<"]="<<v[i]<<endl;
       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';
    //system("PAUSE");
    cin.close();
    cout.close();
    return 0;
}