Cod sursa(job #2472950)

Utilizator sygAndreiIonitaIonita Andrei sygAndreiIonita Data 13 octombrie 2019 11:36:35
Problema Secventa Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.82 kb
#include <bits/stdc++.h>

using namespace std;

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

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

int main()
{
    int n,k,i,nr=1,semn=1,fin,st;
    long long max1=-2000000000;
    char c;
    in>>n>>k;
    in.get(c);
    while (in.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,st=i-k+1,fin=i;
    }
    out<<st<<" "<<fin<<" "<<max1;
    return 0;
}