Cod sursa(job #1386530)

Utilizator timicsIoana Tamas timics Data 13 martie 2015 01:33:45
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include<fstream>
#include<string>
using namespace std;
int N,K,a[500050],d[500050],ind;
string s;

inline void parse() {
    int sgn =  1;
    int curr = 1;
    int nr = 0;
    for(int i=0;i<=s.size();++i) {
        if(i==s.size() || s[i] == ' ' ) {
            a[curr++] = nr*sgn;
            nr = 0;
            sgn = 1;
        } else if(s[i]=='-') {
            sgn = -1;
        } else {
            nr = nr*10 + (s[i]-'0');
        }
    }
}

int main()
{
    ifstream fin("secventa.in");
    ofstream fout("secventa.out");
    fin>>N>>K;
    getline(fin,s);
    getline(fin,s);
    parse();    
    
    int f=1;
    int b=0;
    int ma=-30001;
    for(int i=1;i<=N;++i)
    {
        while((f<=b)&&(a[i]<=a[d[b]]))
            --b;
        ++b;
        d[b]=i;
        if(d[f]==i-K)
            ++f;
        if(i>=K)
            if(a[d[f]]>ma)
            {
                ma=a[d[f]];
                ind=i;
            }
    }
    fout<<ind-K+1<<" "<<ind<<" "<<ma;
    return 0;
}