Cod sursa(job #1779955)

Utilizator tiberiu.bucur17Tiberiu Constantin Emanoil Bucur tiberiu.bucur17 Data 15 octombrie 2016 18:51:11
Problema Heavy metal Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 1.75 kb
#include <stdio.h>
#include <ctype.h>
#define max(a,b) a>b? a:b
#define BUF_SIZE 131072
struct trupa
{
    int st,dr;
}v[100000];
inline int lung(int i)
{
    return v[i].dr-v[i].st;
}
FILE *fin,*fout;
char buf[BUF_SIZE];
int pos=BUF_SIZE;
inline char getch()
{
    if(pos==BUF_SIZE)
        fread(buf,BUF_SIZE,1,fin),pos=0;
    return buf[pos++];
}
inline int read()
{
    int x=0;
    char ch=getch();
    while(!isdigit(ch))
        ch=getch();
    do
    {
        x=x*10+ch-'0';
        ch=getch();
    } while(isdigit(ch));
    return x;
}
inline void interschimb(int *a,int *b)
{
    int aux=*a;
    *a=*b;*b=aux;
}
void myqsort(int start,int stop)
{
    int i,j,p1,p2;
    i=start;j=stop;p1=v[(i+j)/2].st;p2=v[(i+j)/2].dr;
    while(i<=j)
    {
        while(v[i].st<p1)
            i++;
        if(v[i].st==p1)
            while(v[i].dr<p2)
                i++;
        while(v[j].st>p1)
            j--;
        if(v[j].st==p1)
            while(v[j].dr>p2)
                j--;
        if(i<=j)
        {
            interschimb(&v[i].st,&v[j].st);
            interschimb(&v[i].dr,&v[j].dr);
            i++;j--;
        }
    }
    if(j>start)
        myqsort(start,j);
    if(i<stop)
        myqsort(i,stop);
}
int main()
{
    fin=fopen("heavymetal.in","r");
    fout=fopen("heavymetal.out","w");
    int n,i,d1,d2;
    n=read();
    for(i=0;i<n;i++)
    {
        v[i].st=read();
        v[i].dr=read();
    }
    myqsort(0,n-1);
    d1=lung(0);
    for(i=1;i<n;i++)
    {
        if(v[i].st<v[i-1].dr)
            d2=max(d1,d1+lung(i)-lung(i-1));
        else
            d2=d1+lung(i);
        d1=d2;
    }
    fprintf(fout,"%d",d2);
    fclose(fin);
    fclose(fout);
    return 0;
}