Pagini recente » Cod sursa (job #2066217) | Cod sursa (job #56087) | Cod sursa (job #1475028) | Cod sursa (job #1611575) | Cod sursa (job #1711884)
#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){
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\n", itv);
fclose(fi);
fclose(fo);
return 0;
}