Pagini recente » Cod sursa (job #990829) | Cod sursa (job #2680257) | Cod sursa (job #2570054) | Cod sursa (job #1049497) | Cod sursa (job #137381)
Cod sursa(job #137381)
#include <stdio.h>
#define l 100010
int i,j,k,n,m;
long long sum=0;
int a[l][2],b[l][2],poz[l];
void inter(int p, int q)
{
int r=(p+q)/2,x,y,k=0;
x=p;y=r+1;
while (x<=r && y<=q)
{
k++;
if (a[x][1]<a[y][1]) {b[k][0]=a[x][0];b[k][1]=a[x][1];x++;}
else {b[k][0]=a[y][0];b[k][1]=a[y][1];y++;}
}
while (x<=r) {k++;b[k][0]=a[x][0];b[k][1]=a[x][1];x++;}
while (y<=q) {k++;b[k][0]=a[y][0];b[k][1]=a[y][1];y++;}
k=0;
for (i=p; i<=q; i++) { k++;a[i][0]=b[k][0];a[i][1]=b[k][1];}
}
void inter2(int p, int q)
{
int r=(p+q)/2,x,y,k=0;
x=p;y=r+1;
while (x<=r && y<=q)
{
k++;
if (a[x][0]<a[y][0]) {b[k][0]=a[x][0];b[k][1]=a[x][1];x++;}
else {b[k][0]=a[y][0];b[k][1]=a[y][1];y++;}
}
while (x<=r) {k++;b[k][0]=a[x][0];b[k][1]=a[x][1];x++;}
while (y<=q) {k++;b[k][0]=a[y][0];b[k][1]=a[y][1];y++;}
k=0;
for (i=p; i<=q; i++) { k++;a[i][0]=b[k][0];a[i][1]=b[k][1];}
}
void merge(int p, int q, int k)
{
int r=(p+q)/2;
if (p==q) return;
merge(p,r,k);
merge(r+1,q,k);
if (k==0) inter(p,q);
else inter2(p,q);
if (p>=q) return;
}
int main()
{
freopen("heavymetal.in","r",stdin);
freopen("heavymetal.out","w",stdout);
scanf("%d",&n);
for (i=1; i<=n; i++)
scanf("%d %d",&a[i][0],&a[i][1]);
merge(1,n,0);
i=0;
while (i<n)
{
i++;
if (i==n+1) break;
k=i;
while (a[i][1]==a[i+1][1] && i<n) i++;
if (i>k) i--;
if (i!=k) merge(k,i,1);
}
m=1;poz[1]=1;
for (i=2; i<=n; i++)
if (a[i][0]>=a[poz[m]][1])
{
m++;
poz[m]=i;
}
poz[0]=a[1][0];poz[m+1]=n+1;a[n+1][0]=a[n][1];
for (i=m; i>=1; i--)
{
k=a[i][1]-a[i][0];
for (j=poz[i]; j<=poz[i+1]-1; j++)
if (a[poz[i+1]][0]>=a[j][1] && a[j][0]>=a[poz[i-1]][1] && a[j][1]-a[j][0]>k)
{
k=a[j][1]-a[i][0];
poz[i]=j;
}
}
sum=0;
for (i=1; i<=m; i++)
sum+=a[poz[i]][1]-a[poz[i]][0];
printf("%lld\n",sum);
return 0;
}