Pagini recente » Cod sursa (job #1149492) | Cod sursa (job #1048605) | Cod sursa (job #734292) | Cod sursa (job #305291) | Cod sursa (job #1847142)
#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;
}