Cod sursa(job #1808241)

Utilizator blackmanta45Andrei blackmanta45 Data 17 noiembrie 2016 15:55:21
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin ("secventa.in");
ofstream fout ("secventa.out");
short v[500010],minim=-31000,j,nr;
int semn;
int n,k,i,D[500010],pozj,p,u,pozi,m,val;
char S[4000000];
int main () {
    fin>>n>>k;
    fin.get();
    fin.get(S, 4000000);
    semn = 1;
    for(i=1;S[i-1]!=0;i++){
        if (S[i] == '+') {
            semn = 1;
            continue;
        }
        if (S[i] == '-') {
            semn = -1;
            continue;
        }

        if (S[i] >= '0' && S[i] <= '9') {
            val = val * 10 + S[i] - '0';
            continue;
        }
        if ( (S[i] == ' ' || S[i] == '\n' || S[i] == 0) && S[i-1] >= '0' && S[i-1] <= '9') {
            v[++m] = val*semn;
            val = 0;
            semn = 1;
        }
    }

    p=1;
    u=1;
    D[1]=1;
    for(i=2;i<=n;i++){
        while(v[i]<=v[D[u]] && p<=u)
            u--;
        D[++u]=i;
        if(i-D[p]>=k)
            p++;
        if(i>=k && v[D[p]]>minim){
            minim=v[D[p]];
            pozi=i-k+1;
            pozj=i;
        }

    }
    fout<<pozi<<" "<<pozj<<" "<<minim;
}