Cod sursa(job #2208702)

Utilizator caesar2001Stoica Alexandru caesar2001 Data 30 mai 2018 23:37:10
Problema Secventa Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
#include <fstream>

using namespace std;
FILE *in,*out;

const int NMAX = 500005;
int deq[NMAX], v[NMAX];

int main()
{
    in = fopen("secventa.in","r");
    out = fopen("secventa.out","w");
    int n, k;
    fscanf(in,"%d %d", &n, &k);
    for(int i = 1; i <= n; i ++)
        fscanf(in, "%d", &v[i]);
    int st = 1, dr = 1;
    deq[1] = 1;
    int sol = -30005, rsol = 1, lsol = 1;
    for(int i = 2; i <= n; i ++) {
        while(st <= dr && v[i] < v[deq[dr]])
            dr --;
        deq[++dr] = i;
        if(k <= i && sol < v[deq[st]]) {
            sol = v[deq[st]];
            rsol = i;
            lsol = i - k + 1;
        }
        if(deq[dr] - deq[st] == k-1)
            st ++;
    }
    fprintf(out,"%d %d %d", lsol, rsol, sol);
    return 0;
}