Cod sursa(job #1310716)

Utilizator pepsiM4A1Ozturk Arif pepsiM4A1 Data 7 ianuarie 2015 09:00:29
Problema Heavy metal Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 kb
#include <stdio.h>
#include <algorithm>
int n;
struct str
{
       int x1;
       int x2;
}a[100001];
bool vis[100001];
int comp(str a,str b)
{
    if(a.x1!=b.x1) return a.x1<b.x1;
    else return a.x2<b.x2;
}
int inc[100001];
int main()
{
    FILE *fin,*fout;
    fin=fopen("heavymetal.in","r");
    fout=fopen("heavymetal.out","w");
    fscanf(fin,"%d",&n);
    for(int i=0;i<n;i++)
    {
            fscanf(fin,"%d%d",&a[i].x1,&a[i].x2);
    }
    std::sort(a,a+n,comp);
    int pos,pos2;
    for(int i=0;i<n;i++)
    {
            inc[a[i].x1]=a[i].x2;
    }
    int maxim=0,sum;
    for(int i=0;i<n;i++)
    {
            if(vis[i]==0)
            {
                         vis[i]=1;
                         sum=0;
                         pos=a[i].x1;
                         while(1)
                         {
                                 pos2=inc[pos];
                                 if(pos2==0) 
                                 {
                                             pos2=inc[pos+1];
                                             pos++;
                                             if(pos2==0)  break;
                                 }
                                 sum+=(pos2-pos);
                                 vis[pos2]=1;
                                 pos=pos2;
                         }
                         if(maxim<sum) maxim=sum;
            }
    }
    fprintf(fout,"%d\n",maxim);
    fclose(fin);
    fclose(fout);
    return 0;
}