Cod sursa(job #1801663)

Utilizator tanasaradutanasaradu tanasaradu Data 9 noiembrie 2016 14:36:59
Problema Secventa Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 kb
#include <bits/stdc++.h>
#define infinit 1000000
using namespace std;
ifstream fin("secventa.in");
ofstream fout("secventa.out");
char ch[2000005];
int n,k,a[500005];
deque<int>q;
void Citire()
{
    int i,j=0,numar,semn=1;
    fin>>n>>k;
    ///parsare
    fin.get();
    fin.getline(ch,2000005);
    for(i=0;ch[i];)
    {
        if(ch[i]==' ')
            i++;
    else if(ch[i]=='-')
    {
        i++;
        semn=-1;
    }
      else if('0'<=ch[i] and ch[i]<='9')
      {
          numar=0;
          while('0'<=ch[i] and ch[i]<='9')
          {
              numar=numar*10+ch[i]-'0';
              i++;
          }
          a[++j]=numar*semn;
          semn=1;
      }
    }
}
void Rezolvare()
{
    int x,i,maxim,init,sfarsit;
    for(i=1;i<=k;i++)
    {
        x=a[i];
        while(!q.empty() and a[q.back()]>=x)
            q.pop_back();
        q.push_back(i);
    }
    maxim=a[q.front()];
    init=1;
    sfarsit=k;
    for(i=k+1;i<=n;i++)
    {
        x=a[i];
        while(!q.empty() and a[q.back()]>=x)
            q.pop_back();
        q.push_back(i);
        if(i-q.front()>=k)
            q.pop_front();
        if(maxim<a[q.front()] and i>=k)
        {
            maxim=a[q.front()];
            init=q.front();
            sfarsit=i;
        }
    }
    fout<<init<<" "<<sfarsit<<" "<<maxim<<"\n";
}
int main()
{
    Citire();
    Rezolvare();
    return 0;
}