Cod sursa(job #1014459)

Utilizator stefanzzzStefan Popa stefanzzz Data 22 octombrie 2013 18:55:22
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <fstream>
#include <deque>
#define MAXN 500005
#define INF 50000
#define MAXC 3700000
using namespace std;
ifstream f("secventa.in");
ofstream g("secventa.out");

int n,k,v[MAXN],mx,mxi,cnt,x;
char s[MAXC];
bool neg;
deque<int> dq;

int getnr();

int main()
{
    int i;
    f>>n>>k;
    mx=-INF;
    f.getline(s,MAXC,'\n');
    f.getline(s,MAXC,'\n');
    for(i=1;i<=n;i++)
        v[i]=getnr();
    for(i=1;i<=k-1;i++){
        while(!dq.empty()&&v[dq.back()]>=v[i])
            dq.pop_back();
        dq.push_back(i);}
    for(i=k;i<=n;i++){
        while(!dq.empty()&&v[dq.back()]>=v[i])
            dq.pop_back();
        dq.push_back(i);
        while(dq.front()<i-k+1)
            dq.pop_front();
        if(v[dq.front()]>mx){
            mx=v[dq.front()];
            mxi=i;}}
    g<<mxi-k+1<<' '<<mxi<<' '<<mx<<'\n';
    f.close();
    g.close();
    return 0;
}

int getnr(){
    neg=0;
    if(s[cnt]=='-'){
        ++cnt;
        neg=1;}
    x=s[cnt++]-'0';
    while(s[cnt]>='0'&&s[cnt]<='9')
        x=x*10+s[cnt++]-'0';
    cnt++;
    if(neg)
        x*=(-1);
    return x;}