Cod sursa(job #2055348)

Utilizator Consti.001FMI Dranca Constantin Consti.001 Data 3 noiembrie 2017 08:57:07
Problema A+B Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 kb
#include<fstream>
#include<algorithm>
#include<iostream>
#include <vector>
#include <queue>
using namespace std;

ifstream f("data.in");
ofstream g("data.out");


struct interval
{
    int left,right;
    int grupa;
    bool operator >(const interval& a) const
    {
        return right>a.right;
    }
};

bool cmp(interval a, interval b)
{
    return a.left<b.left;
}
int main()
{
    int n;
    f>>n;

    interval lista[n+1];
    for(int i=0;i<n;++i)
    {
        f>>lista[i].left>>lista[i].right;
    }
    sort(lista,lista+n,cmp);

    vector <interval> multimi[n+1];
    int m=0;
    priority_queue <interval(), vector<interval> , greater<interval> > q;

    ++m;
    lista[0].grupa=m;
    multimi[m].push_back(lista[0]);
    q.push(lista[0]);
    for(int i=1;i<n;++i)
    {
        if(q.top().right>lista[i].left)
        {
            ++m;
            lista[i].grupa=m;
            multimi[m].push_back(lista[i]);
            q.push(lista[i]);
        }
        else
        {
            lista[i].grupa=q.top().grupa;
            multimi[q.top().grupa].push_back(lista[i]);
            q.pop();
            q.push(lista[i]);
        }
    }
    g<<m<<"\n";
    for(int i=1;i<=m;++i)
    {
        g<<"Multimea "<<i<<": ";
        for(unsigned int j=0;j<multimi[i].size();++j)
        g<<"("<<multimi[i][j].left<<","<<multimi[i][j].right<<"); ";
        g<<"\n";
    }
    return 0;
}