Cod sursa(job #1485776)

Utilizator bogdanboboc97Bogdan Boboc bogdanboboc97 Data 12 septembrie 2015 22:20:43
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <vector>
#include <set>
#include <limits>
#define INF numeric_limits<int>::max()
#define pb push_back
#define mp make_pair
using namespace std;
//ifstream in("secventa.in");
ofstream out("secventa.out");
int n,k,a[500005],dq[500005];
int main()
{
    freopen("secventa.in","r",stdin);
    scanf("%d%d",&n,&k);
    //in>>n>>k;
    //for(int i=1;i<=n;i++)
        //scanf("%d",&a[i]);
        //in>>a[i];
    int lf=1,rt=0,mx=-INF,x,y;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        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;
}