Cod sursa(job #1860862)

Utilizator adystar00Bunea Andrei adystar00 Data 28 ianuarie 2017 14:03:53
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
struct eu {int st,dr;};
eu v[100010];
int s[100010];
int poz[100010];
bool cmp (eu a, eu b)
{
    if(a.st<b.st)
        return true;
    if(a.st>b.st)
        return false;
    if(a.st==b.st)
    {
        if(a.dr<b.dr)
            return true;
        return false;
    }
}
int main()
{
    ifstream fin ("heavymetal.in");
    ofstream fout ("heavymetal.out");
    int maxx=0,i,nr=0,pz,j,st,dr,mij,ans=0,n;
    fin>>n;
    for(i=1;i<=n;i++)
        fin>>v[i].st>>v[i].dr;
    sort(v+1,v+n+1,cmp);
    poz[1]=1;
    s[1]=1;
    nr=1;
    for(i=2;i<=n;i++)
    {
        if(v[i].st>maxx)
        {
            nr++;
            s[nr]=i;
            maxx=v[i].dr;
            poz[i]=nr;
        }
        else
        {
            st=1;
            dr=nr;
            while(st<=dr)
            {
                mij=(st+dr)/2;
                if(v[mij].dr>v[i].st)
                    dr=mij-1;
                else
                    st=mij+1;
            }
            poz[i]=mij;
            s[mij]=i;
        }
    }
    int k=nr;
    for(i=n;i>=1;i--)
    {
        if(poz[i]==k)
        {
            k--;
            ans+=v[i].dr-v[i].st;
        }
    }
    fout<<ans;
    return 0;
}