Cod sursa(job #2187222)

Utilizator MarutBrabete Marius Stelian Marut Data 26 martie 2018 12:19:55
Problema Arbori de intervale Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.12 kb
#include <cstdio>
#include <algorithm>

using namespace std;

struct hoti{int st,dr,paz,nr;};
struct bat{int sa,da;};

bool cmp(hoti a,hoti b)
{
    if(a.dr<b.dr)
    {
        return true;
    }
    else
    {
        if(a.dr==b.dr)
        {
            if(a.st<b.st)
            {
                return true;
            }
            else
            {
                return false;
            }
        }
        else
        {
            return false;
        }
    }
}
bool smp(hoti a,hoti b)
{
    if(a.nr<b.nr)
    {
        return true;
    }
    else
    {
        return false;
    }
}
int main()
{
    freopen("sant1.in","r",stdin);
    freopen("sant1.out","w",stdout);
    int n,i,ct,s,d,j;
    hoti v[10001];
    bat va[10001];
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%d %d",&s,&d);
        v[i].nr=i;
        v[i].st=s;
        v[i].dr=d;
    }
    sort(v+1,v+1+n,cmp);
    ct=1;
    v[1].paz=ct;
    for(i=1;i<=n;i++)
    {
        if(v[i].st!=2000 && v[i].dr!=2000)
        {
            s=v[i].st;
            d=v[i].dr;
            j=i;
            while(s<=d && j<=n)
            {
                if(v[j].st>s)
                {
                    s=v[j].st;
                }
                if(v[i].dr<d)
                {
                    d=v[j].dr;
                }
                if(s<=d)
                {
                    v[j].st=2000;
                    v[j].dr=2000;
                    v[j].paz=ct;
                    va[ct].sa=s;
                    va[ct].da=d;
                }
                else
                {
                    ct++;
                }
                j++;
            }
        }
    }
    //v[j-1].paz=ct;
    va[ct].sa=s;
    va[ct].da=d;
    printf("%d\n",ct);
    sort(v+1,v+1+n,smp);
    for(i=1;i<=ct;i++)
    {
        printf("%d %d %d\n",i,va[i].sa,va[i].da);
        for(j=1;j<=n;j++)
        {
            if(v[j].paz==i)
            {
                printf("%d ",v[j].nr);
            }
        }
        printf("\n");
    }

    return 0;
}