Pagini recente » Cod sursa (job #816722) | Cod sursa (job #1987426) | Cod sursa (job #3159502) | Cod sursa (job #1213423) | Cod sursa (job #346761)
Cod sursa(job #346761)
#include <stdio.h>
using namespace std;
int heap[500000][2], poz[500000], elem=0;
void addheap(int f, int i);
void deleteheap(int pozina);
int min(int a, int b);
int main() {
int n, k, i, j, min1, min, a[500000], start;
FILE *in=fopen("secventa.in", "r"), *out=fopen("secventa.out", "w");
fscanf(in, "%d%d", &n, &k);
for(i=1; i<=n; i++) {
fscanf(in, "%d", &a[i]);
}
for(i=1; i<=k; i++) {
poz[i]=elem+1;
addheap(a[i], i);
}
min1=heap[1][0]; start=1;
for(i=2; i<=n-k+1; i++) {
deleteheap(i-1);
poz[i+k-1]=elem+1;
addheap(a[i+k-1], i+k-1);
/*
for(j=1; j<=elem; j++) {
printf("%d ", heap[j][0]);
}
printf("\n\n");
*/
min=heap[1][0];
if(min>min1) {
min1=min;
start=i;
}
}
fprintf(out, "%d %d %d", start, start+k-1, min1);
fclose(in); fclose(out);
return 0;
}
int min(int a, int b) {
if(a<b) return a;
else return b;
}
void addheap(int f, int i) {
int s, k;
elem++;
heap[elem][0]=f; heap[elem][1]=i;
s=elem;
while(s>1 && heap[s][0]<heap[s/2][0]) {
poz[heap[s][1]]=s/2;
poz[heap[s/2][1]]=s;
k=heap[s][0]; heap[s][0]=heap[s/2][0]; heap[s/2][0]=k;
k=heap[s][1]; heap[s][1]=heap[s/2][1]; heap[s/2][1]=k;
s=s/2;
}
}
void deleteheap(int pozina) {
int w, p, s, k;
p=poz[pozina];
heap[p][0]=heap[elem][0]; heap[p][1]=heap[elem][1];
heap[elem][0]=30001;
poz[heap[p][1]]=elem;
poz[heap[elem][1]]=p;
elem--;
s=p;
while(s<elem && heap[s][0]>min(heap[s*2][0], heap[s*2+1][0])) {
if(heap[s*2][0]<heap[s*2+1][0]) {
w=s*2;
}
else {
w=s*2+1;
}
poz[heap[w][1]]=s; poz[heap[s][1]]=w;
k=heap[s][0]; heap[s][0]=heap[w][0]; heap[w][0]=k;
k=heap[s][1]; heap[s][1]=heap[w][1]; heap[w][1]=k;
s=w;
}
}