Cod sursa(job #982830)

Utilizator smaraldaSmaranda Dinu smaralda Data 10 august 2013 11:53:10
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include<stdio.h>
#include<deque>
using namespace std;
struct DEQUE { int pos, val; };

DEQUE make ( int a, int b) {
    DEQUE ret={a,b};
    return ret;
}

deque <DEQUE> q;
int n,k;
int main() {
    freopen("secventa.in","r",stdin);
    freopen("secventa.out","w",stdout);
    int i,pos,baza,x;
    scanf("%d%d",&n,&k);
    for(i=1;i<=k;i++) {
        scanf("%d",&x);
        while(!q.empty() && x < q.back().val)
            q.pop_back();
        q.push_back(make(i,x));
        }

    pos=k;
    baza=q.front().val;
    for(i=k+1; i<=n; i++) {
        if(!q.empty() && q.front().pos <= i-k)
            q.pop_front();
        scanf("%d",&x);
        while(!q.empty() && x < q.back().val)
            q.pop_back();
        q.push_back(make(i,x));
        if(q.front().val > baza) {
            pos=i;
            baza=q.front().val;
            }
        }

    printf("%d %d %d\n",pos-k+1,pos,baza);
    return 0;
}