Cod sursa(job #982832)

Utilizator smaraldaSmaranda Dinu smaralda Data 10 august 2013 12:03:01
Problema Secventa Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include<stdio.h>
#include<deque>
using namespace std;
struct DEQUE { int pos, val; };
char nr[15];

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

deque <DEQUE> q;
int n,k;

void getx (int &x) {
    scanf("%s",nr);
    int i,semn=1;
    if(nr[0]=='-')
        semn=-1,
        i=1;
    else
        i=0;
    for(x=0;nr[i]!=NULL;i++)
        x=x*10+nr[i]-'0';
    x*=semn;
}

int main() {
    freopen("secventa.in","r",stdin);
    freopen("secventa.out","w",stdout);
    int i,pos,baza,x;
    scanf("%d%d\n",&n,&k);
    for(i=1;i<=k;i++) {
        getx(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();
        getx(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;
}