Cod sursa(job #1847142)

Utilizator preda.andreiPreda Andrei preda.andrei Data 14 ianuarie 2017 12:35:22
Problema Secventa Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 2.97 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXN 500000
#define BUFFSIZE 1000

typedef struct Node
{
    int value;
    int position;
    struct Node *prev;
    struct Node *next;
} Node;

typedef struct Deque
{
    Node *begin, *end;
} Deque;

Node* CreateNode(Node *prev, int val, int pos)
{
    Node *node = (Node*)malloc(sizeof(Node));
    node->value = val;
    node->position = pos;

    node->prev = prev;
    node->next = NULL;

    return node;
}

void InitDeque(Deque *d)
{
    d->begin = d->end = NULL;
}

int Empty(Deque *d)
{
    return (d->begin == NULL) ? 1 : 0;
}

void PopEnd(Deque *d)
{
    Node *to_delete = d->end;
    d->end = d->end->prev;

    if (d->end) {
        d->end->next = NULL;
    } else {
        d->begin = NULL;
    }

    free(to_delete);
}

void PopBegin(Deque *d)
{
    Node *to_delete = d->begin;
    d->begin = d->begin->next;

    if (d->begin) {
        d->begin->prev = NULL;
    } else {
        d->end = NULL;
    }

    free(to_delete);
}

void Insert(Deque *d, int val, int pos)
{
    while (!Empty(d) && d->end->value >= val) {
        PopEnd(d);
    }

    Node *new_node = CreateNode(d->end, val, pos);
    if (d->end) {
        d->end->next = new_node;
        d->end = new_node;
    } else {
        d->begin = d->end = new_node;
    }
}

int vec[MAXN + 1];
char str[BUFFSIZE + 5];

int ReadInt(FILE *f)
{
    static int pos = BUFFSIZE;
    int num = 0;
    int sign = 1;

    if (pos >= BUFFSIZE - 1) {
        fgets(str, BUFFSIZE, f);
        pos = 0;
    }

    while (str[pos] < '0' || str[pos] > '9') {
        if (str[pos] == '-') {
            sign = -1;
        }
        ++pos;
        if (pos >= BUFFSIZE - 1) {
            fgets(str, BUFFSIZE, f);
            pos = 0;
        }
    }

    while (str[pos] >= '0' && str[pos] <= '9') {
        num = num * 10 + (str[pos] - '0');
        ++pos;
        if (pos >= BUFFSIZE - 1) {
            fgets(str, BUFFSIZE, f);
            pos = 0;
        }
    }

    return num * sign;
}

int main()
{
    FILE *fin = fopen("secventa.in", "r");
    FILE *fout = fopen("secventa.out", "w");

    int n, k, i;
    fscanf(fin, "%d%d%*c", &n, &k);

    Deque deq;
    InitDeque(&deq);

    for (i = 1; i <= k; ++i) {
        vec[i] = ReadInt(fin);
        Insert(&deq, vec[i], i);
    }

    int end_pos = k, base = deq.begin->value;
    for (i = k + 1; i <= n; ++i) {
        vec[i] = ReadInt(fin);
        Insert(&deq, vec[i], i);

        while (!Empty(&deq) && deq.begin->position <= i - k) {
            PopBegin(&deq);
        }

        if (deq.begin->value > base) {
            base = deq.begin->value;
            end_pos = i;
        }
    }

    int start_pos = end_pos - k + 1;
    while (start_pos > 1 && vec[start_pos - 1] >= base) {
        --start_pos;
    }

    fprintf(fout, "%d %d %d\n", start_pos, end_pos, base);
    return 0;
}