Cod sursa(job #1780107)

Utilizator tiberiu.bucur17Tiberiu Constantin Emanoil Bucur tiberiu.bucur17 Data 15 octombrie 2016 20:51:48
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <cstdio>
#include <cctype>
#include <algorithm>
#define MAXN 100000
#define BUF_SIZE 131072
using namespace std;
struct trupa
{
    int st,dr;
}v[MAXN];
int d[MAXN],pos=BUF_SIZE,n,poz[MAXN];
inline int lung(int i)
{
    return v[poz[i]].dr-v[poz[i]].st;
}
FILE *fin,*fout;
char buf[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;
}
bool cond(int a,int b)
{
    return v[a].dr<v[b].dr || (v[a].dr==v[b].dr && v[a].st<v[b].st);
}
inline int cbin(int x)
{
    int i,j,mij;
    i=0;j=n-1;
    while(i<=j)
    {
        mij=(i+j)/2;
        if(v[poz[mij]].dr==x)
        {
            while(v[poz[mij]].dr==x)
                mij++;
            return mij-1;
        }
        if(v[poz[mij]].dr<x)
            i=mij+1;
        else
            j=mij-1;
    }
    return j;
}
int main()
{
    fin=fopen("heavymetal.in","r");
    fout=fopen("heavymetal.out","w");
    int i;
    n=read();
    for(i=0;i<n;i++)
    {
        v[i].st=read();
        v[i].dr=read();
        poz[i]=i;
    }
    sort(poz,poz+n,cond);
    d[0]=lung(0);
    for(i=1;i<n;i++)
        d[i]=max(d[i-1],d[cbin(v[poz[i]].st)]+lung(i));
    fprintf(fout,"%d",d[n-1]);
    fclose(fin);
    fclose(fout);
    return 0;
}