Cod sursa(job #1485778)

Utilizator bogdanboboc97Bogdan Boboc bogdanboboc97 Data 12 septembrie 2015 22:32:30
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <vector>
#include <set>
#include <limits>
#include <string>
#define INF numeric_limits<int>::max()
#define pb push_back
#define mp make_pair
#define val(x) (x-'0')
using namespace std;
ifstream in("secventa.in");
ofstream out("secventa.out");
int n,k,a[500005],dq[500005],pos;
string s;
int nextInt()
{
    int nr=0,sgn=1;
    while(s[pos]==' ')pos++;
    if(s[pos]=='-')
    {
        sgn=-1;
        pos++;
    }
    while(s[pos]>='0' && s[pos]<='9')
    {
        nr=nr*10+val(s[pos]);
        pos++;
    }
    return nr*sgn;
}
int main()
{
    in>>n>>k;
    in.get();
    getline(in,s);
    int lf=1,rt=0,mx=-INF,x,y;
    for(int i=1;i<=n;i++)
    {
        a[i]=nextInt();
        while(lf<=rt && a[i]<=a[dq[rt]])rt--;
        dq[++rt]=i;
        if(dq[lf]==i-k)lf++;
        if(i>=k && mx<a[dq[lf]])
        {
            mx=a[dq[lf]];
            x=i-k+1;
            y=i;
        }
    }
    out<<x<<' '<<y<<' '<<mx<<'\n';
    return 0;
}