Cod sursa(job #1274998)

Utilizator lokixdSebastian lokixd Data 24 noiembrie 2014 17:28:31
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <iostream>
#include <fstream>
#include <cstring>
 
using namespace std;
 
ifstream f("secventa.in");
ofstream g("secventa.out");
 
const int NMax = 500010;
const int CMax = 5000002;
int v[NMax],d[NMax];
char nr[NMax];
 
void chg()
{
    int semn,j,r;
    j = 1;
    for(int i = 0; nr[i] != 0; i++){
        semn = 1;
        r = 0;
        if(nr[i] == '-'){
            semn = -1;
            i++;
        }
        while(nr[i] >= '0' && nr[i] <= '9'){
            r = r * 10 + nr[i] - '0';
            i++;
        }
        v[j] = r * semn;
        j++;
    }
}
int main()
{
    int n,k,p,u,pz,mx;
    f >> n >> k;
    f.get();
    f.getline(nr,CMax);
    chg();
    p = 1;
    u = 0;
    mx = - NMax;
    pz = k;
    for(int i = 1; i <= n; i++){
        while(p <= u && v[i] <= v[d[u]]) u--;
        d[++u] = i;
        if(d[p] == i - k)
            p++;
        if(i >= k && v[d[p]] > mx){
            mx = v[d[p]];
            pz = i;
        }
    }
    g << pz - k + 1 << " " << pz << " " << mx;
    return 0;
}