Pagini recente » Cod sursa (job #2313551) | Cod sursa (job #2422836) | Cod sursa (job #1629450) | Cod sursa (job #2963796) | Cod sursa (job #206686)
Cod sursa(job #206686)
#include <stdio.h>
#include <string.h>
#define MAX 500010
int a[MAX], left[MAX], right[MAX];
int n, k;
int best_start, best_end, best_base;
void read(void) {
FILE *f = fopen("secventa.in", "rt");
fscanf(f, "%d %d", &n, &k);
for (int i = 0; i < n; i++) {
fscanf(f, "%d", &a[i]);
}
fclose(f);
}
void compute_right() {
int sp = 0;
int stack[MAX];
for (int i = 0; i < n; i++) {
while (sp && (a[i] < a[stack[sp - 1]])) {
right[stack[sp - 1]] = i - stack[sp - 1] - 1;
sp--;
}
stack[sp++] = i;
}
while (sp) {
right[stack[sp - 1]] = n - stack[sp - 1] - 1;
sp--;
}
}
void compute_left() {
int sp = 0;
int stack[MAX];
for (int i = n - 1; i >= 0; i--) {
while (sp && (a[i] < a[stack[sp - 1]])) {
left[stack[sp - 1]] = stack[sp - 1] - i - 1;
sp--;
}
stack[sp++] = i;
}
while (sp) {
right[stack[sp - 1]] = stack[sp - 1] - 1;
sp--;
}
}
void scan(void) {
best_base = -1000000;
for (int i = 0; i < n; i++) {
if (left[i] + right[i] + 1 >= k) {
int start = i - left[i];
int end = start + k - 1;
if ((a[i] > best_base) ||
((a[i] == best_base) &&
(start <= best_start)) ||
((a[i] == best_base) &&
(start == best_start) &&
(end < best_end))) {
best_base = a[i];
best_start = start;
best_end = end;
}
}
}
}
void write() {
FILE *f = fopen("secventa.out", "wt");
fprintf(f, "%d %d %d\n", best_start + 1, best_end + 1, best_base);
fclose(f);
}
int main() {
read();
compute_right();
compute_left();
scan();
write();
return 0;
}