Cod sursa(job #1711882)

Utilizator andreicoman299Coman Andrei andreicoman299 Data 1 iunie 2016 14:18:16
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <stdio.h>
#include <stdlib.h>

int v[200000][2], w[200000][2];
void myqsort( int begin, int end){
  int b = begin, e = end;
  int aux, pivot = v[begin + rand() % (end - begin + 1)][0];

  while ( b <= e ) {
    while ( v[b][0] < pivot ) b++;
    while ( v[e][0] > pivot ) e--;
    if ( b <= e ) {
      aux = v[b][0]; v[b][0] = v[e][0]; v[e][0] = aux;
      aux = v[b][1]; v[b][1] = v[e][1]; v[e][1] = aux;
      b++; e--;
    }
  }

  if ( begin < e ) myqsort( begin, e);
  if ( b < end ) myqsort( b, end);
}

int main(){
    int n;
    FILE*fi,*fo;
    fi=fopen("heavymetal.in","r");
    fo=fopen("heavymetal.out","w");
    fscanf(fi,"%d", &n);
    for(int i=0;i<n;i++){
        fscanf(fi,"%d%d", &v[2*i][0], &v[2*i+1][0]);
        v[2*i][1]=1;
        v[2*i+1][1]=-1;
    }
    myqsort(0, 2*n-1);
    int ind=0, prev=0;
    w[0][0]=v[0][0];
    w[0][1]=v[0][1];
    for(int i=1;i<2*n;i++){
        if(v[i][0]==v[i-1][0])
            w[ind][1]+=v[i][1];
        else{
            ind++;
            w[ind][0]=v[i][0];
            w[ind][1]=v[i][1];
        }
    }
    int sum=w[0][1], itv=0;
    int j=1;
    while(j<=ind){
        //printf("%d %d\n", w[j][0], sum);
        if(sum==0){
            while(j<=ind && sum==0)
                sum+=w[j++][1];
        }
        else{
            prev=j-1;
            while(j<=ind && sum>0)
                sum+=w[j++][1];
            itv+=w[j-1][0]-w[prev][0];
        }
    }
    fprintf(fo,"%d", itv);
    fclose(fi);
    fclose(fo);
    return 0;
}