Cod sursa(job #346761)

Utilizator vladiiIonescu Vlad vladii Data 9 septembrie 2009 15:18:14
Problema Secventa Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.3 kb
#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;
     }
}