Cod sursa(job #982836)

Utilizator smaraldaSmaranda Dinu smaralda Data 10 august 2013 12:07:56
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include<stdio.h>
#include<deque>
#include<ctype.h>
using namespace std;
struct DEQUE { int pos, val; };
char ln[3500010];

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

deque <DEQUE> q;
int n,k,p;

void getx (int &x) {
    int i,semn=1;
    if(ln[p]=='-')
        semn=-1,
        ++p;
    for(x=0; isdigit(ln[p]); p++)
        x=x*10+ln[p]-'0';
    x*=semn;
    p++;
}

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