Cod sursa(job #2485825)

Utilizator paul3ioanCirstean Paul Ioan paul3ioan Data 2 noiembrie 2019 09:31:42
Problema Secventa Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <bits/stdc++.h>

using namespace std;

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

deque < pair<int,int> > d;
int v[500001];

int main()
{
    int n,k,i,nr=1,semn=1,sf,inc;
    long long max1=-2000000000;
    char c;
    fin>>n>>k;
        fin.get(c);
    while (fin.get(c)&&c!='\n')
    {
      if (isdigit(c))
        v[nr]=v[nr]*10+c-'0';
      else if (c=='-')
        semn=-1;
      else
        v[nr]*=semn,semn=1,nr++;
    }
    v[nr]*=semn;

    for (i=1;i<=n;i++)
    {
      while (!d.empty()&&v[i]<=d.back().first)
            d.pop_back();
      d.push_back(make_pair(v[i],i));
      if (d.front().second==i-k)
        d.pop_front();
      if (i>=k&&d.front().first>max1)
        max1=d.front().first,inc=i-k+1,sf=i;
    }
    fout<<inc<<" "<<sf<<" "<<max1;
    return 0;
}