Cod sursa(job #2591915)

Utilizator AlexrotaruRotaru Alexandru Alexrotaru Data 31 martie 2020 17:45:52
Problema Secventa Scor 0
Compilator c-64 Status done
Runda Arhiva de probleme Marime 2.51 kb
#include <stdlib.h>
#include <stdio.h>

#define MAXN 500010

typedef struct deque {
    int *mem_start, *start, *end;
    size_t max_sz, curr_sz;
} t_deque;

#define NEXT(p) ((p) + 1)
#define MEM_END(p) (p->mem_start + p->max_sz)

t_deque *create_deque(size_t size);
void push_back(t_deque *deque, int value);
int pop_back(t_deque *deque);
int pop_front(t_deque *deque);
int get_back(t_deque *deque);
int get_front(t_deque *deque);
int empty(t_deque *deque);

t_deque *create_deque(size_t size)
{
    t_deque *deque;

    deque = (t_deque *) malloc(sizeof(t_deque));
    deque->mem_start = (int *) malloc(size * sizeof(int));
    deque->start = deque->mem_start;
    deque->end = deque->start - 1;
    deque->max_sz = size;
    deque->curr_sz = 0;
    return deque;
}

void push_back(t_deque *deque, int value)
{
    if(deque->curr_sz >= deque->max_sz) {
        return;
    }
    deque->end = NEXT(deque->end);
    if(deque->end == MEM_END(deque)) {
        deque->end = deque->mem_start;
    }
    *(deque->end) = value;
    deque->curr_sz++;
}

int pop_back(t_deque *deque)
{
    int value = *(deque->end);

    if(deque->end == deque->mem_start) {
        deque->end = MEM_END(deque) - 1;
    }
    else {
        deque->end--;
    }
    deque->curr_sz--;
    return value;
}

int pop_front(t_deque *deque)
{
    int value = *(deque->start);

    if(NEXT(deque->start) == MEM_END(deque)) {
        deque->start = deque->mem_start;
    }
    else {
        deque->start = NEXT(deque->start);
    }
    deque->curr_sz--;
    return value;

}
int get_back(t_deque *deque)
{
    return *(deque->end);
}

int get_front(t_deque *deque)
{
    return *(deque->start);
}

int empty(t_deque *deque)
{
    return deque->curr_sz == 0;
}

int v[MAXN];

int main()
{
    FILE *fin = fopen("secventa.in", "r"),
         *fout = fopen("secventa.out", "w");
    t_deque *deque;
    int n, k, i, ic, sf, fr, max = -30001;

    fscanf(fin, "%d %d", &n, &k);
    for(i = 0; i < n; i++) {
        fscanf(fin, "%d", &v[i]);
    }
    deque = create_deque(k + 10);
    for(i = 0; i < n; i++) {
        while(v[get_back(deque)] > v[i] && !empty(deque)) {
            pop_back(deque);
        }
        push_back(deque, i);
        if(i - k == get_front(deque)) {
            pop_front(deque);
        }
        if(i >= k - 1) {
            fr = get_front(deque);
            if(v[fr] > max) {
                max = v[fr];
                ic = fr + 1;
                sf = fr + k;
            }
        }
    }
    fprintf(fout, "%d %d %d", ic, sf, max);
    fclose(fin);
    fclose(fout);
}