Cod sursa(job #1856625)

Utilizator ipus1Stefan Enescu ipus1 Data 25 ianuarie 2017 10:11:10
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include<cstdio>
#include<algorithm>
using namespace std;
struct aa{int x,y;};
aa v[100001],vec[100001];
bool sortare(aa a,aa b)
    {if(a.y<b.y||(a.y==b.y&&a.x<b.x))
        return 1;
    return 0;
    }
int main ()
{freopen ("heavymetal.in","r",stdin);
freopen ("heavymetal.out","w",stdout);
int n,i,c1,c2,x,k=0,q;
scanf("%d",&n);
for(i=1;i<=n;i++)
    {scanf("%d%d",&v[i].x,&v[i].y);
    v[i].y--;
    }
sort(v+1,v+n+1,sortare);
for(i=1;i<=n;i++)
    {c1=1;
    c2=k;
    q=0;
    while(c1<=c2)
        {x=(c1+c2)/2;
        if(vec[x].x<v[i].x&&(vec[x+1].x>=v[i].x||x==k))
            {q=x;
            c1=c2+1;
            }
        else
            if(vec[x].x<v[i].x)
                c1=x+1;
            else
                c2=x-1;
        }
    if(vec[k].x!=v[i].y)
        {k++;
        vec[k].x=v[i].y;
        vec[k].y=max(v[i].y-v[i].x+1+vec[q].y,vec[k-1].y);
        }
    else
        vec[k].y=max(v[i].y-v[i].x+1+vec[q].y,vec[k].y);
    }
printf("%d",vec[k].y);
return 0;
}