Submission #85075

#	Time	Username	Problem	Language	Result	Execution time	Memory
85075		AdrienVannson	Port Facility (JOI17_port_facility)	C++17	100 / 100	2086 ms	559476 KiB

port_facility

#include <algorithm>
#include <iostream>
#include <cstdio>
#include <vector>
#include <set>
#include <stack>

using namespace std;

const int MODULO = 1000*1000*1000+7;

const int NB_MAX_OBJETS = 1000*1000;

template<int NB_NOEUDS>
class UnionFind
{
public:

    UnionFind ()
    {
        for (int iNoeud=0; iNoeud<NB_NOEUDS; iNoeud++) {
            representants[iNoeud] = iNoeud;
            tailles[iNoeud] = 1;
        }
    }

    int representant (const int iNoeud)
    {
        if (representants[iNoeud] == iNoeud) {
            return iNoeud;
        }
        return representants[iNoeud] = representant(representants[iNoeud]);
    }

    int taille (const int iNoeud)
    {
        return tailles[representant(iNoeud)];
    }

    void unir (int iNoeud1, int iNoeud2)
    {
        iNoeud1 = representant(iNoeud1);
        iNoeud2 = representant(iNoeud2);

        if (iNoeud1 == iNoeud2) {
            return;
        }

        if (tailles[iNoeud2] > tailles[iNoeud1]) {
            swap(iNoeud1, iNoeud2);
        }

        tailles[iNoeud1] += tailles[iNoeud2];
        tailles[iNoeud2] = 0;

        representants[iNoeud2] = iNoeud1;
    }

private:
    int representants[NB_NOEUDS];
    int tailles[NB_NOEUDS]; // Valide uniquement pour les racines
};


struct Intervalle
{
    int debut, fin;

    int taille () const
    {
        return fin - debut;
    }

    bool estInclusDans (const Intervalle &autre) const
    {
        return debut >= autre.debut && fin <= autre.fin;
    }

    bool operator< (const Intervalle &autre) const
    {
        if (debut != autre.debut) {
            return debut < autre.debut;
        }
        return fin < autre.fin;
    }
};

Intervalle getUnion (const Intervalle &a, const Intervalle &b)
{
    return Intervalle {min(a.debut, b.debut), max(a.fin, b.fin)};
}

Intervalle getIntersection (const Intervalle &a, const Intervalle &b)
{
    return Intervalle {max(a.debut, b.debut), min(a.fin, b.fin)};
}

bool getAIntersection (const Intervalle &a, const Intervalle &b)
{
    return (a.debut < b.debut && a.fin > b.debut && a.fin < b.fin)
        || (b.debut < a.debut && b.fin > a.debut && b.fin < a.fin);
}


int nbObjets;
Intervalle intervalles[NB_MAX_OBJETS];

UnionFind<2*NB_MAX_OBJETS> unionFind; // Maintient les états équivalents


/*
 * Calcul de la solution optimale
 */

int getPuissance (const int puissance)
{
    int res = 1;

    for (int iPuissance=0; iPuissance<puissance; iPuissance++) {
        res = (res*2) % MODULO;
    }

    return res;
}

int getNbPossibilites ()
{
    sort(intervalles, intervalles+nbObjets, [](const Intervalle &a, const Intervalle &b) {
        return a.fin < b.fin;
    });

    set<Intervalle> pointsRestants;
    for (int iPoint=0; iPoint<nbObjets; iPoint++) {
        pointsRestants.insert(intervalles[iPoint]);
    }

    // Tous les intervalles stockés sont disjoints et représentent une composante connexe
    set< pair<Intervalle, int> > enCours; // {intervalle, etat}
    int nbComposantes = 0;


    for (int iPoint=0; iPoint<nbObjets; iPoint++) {
        pointsRestants.erase(intervalles[iPoint]);

        Intervalle actuel = intervalles[iPoint];
        int etatActuel = 2*iPoint;
        nbComposantes++;


        set<pair<Intervalle, int>>::iterator enContact = enCours.upper_bound( make_pair(actuel, etatActuel) );

        // Vérifier le contact à gauche
        if (enContact != enCours.begin()) {
            enContact--;

            if (enContact->first.fin > actuel.debut) { // Il y a une intersection

                const Intervalle intersection = getIntersection(actuel, enContact->first);

                if (pointsRestants.lower_bound(intersection) != pointsRestants.end()
                 && pointsRestants.lower_bound(intersection)->debut < intersection.fin) { // Impossible

                    return 0;
                }
                else {
                    etatActuel = unionFind.representant(enContact->second ^ 1);
                    nbComposantes--;

                    actuel.debut = enContact->first.fin;

                    if (actuel.taille() <= 0) {
                        continue;
                    }
                }
            }
        }

        // Inclusions ou contact à droite
        enContact = enCours.lower_bound( make_pair(actuel, etatActuel) );

        while (enContact != enCours.end() && enContact->first.debut < actuel.fin) { // Il y a une intersection

            const Intervalle intersection = getIntersection(actuel, enContact->first);
            const Intervalle reunion = getUnion(actuel, enContact->first);
            const int autreEtat = enContact->second;

            if (pointsRestants.lower_bound(intersection) != pointsRestants.end()
             && pointsRestants.lower_bound(intersection)->debut < intersection.fin) { // Fusionner

                if (unionFind.representant(etatActuel) == (unionFind.representant(autreEtat) ^ 1)) {
                    return 0;
                }

                // Marquer les deux états équivalents
                if (unionFind.representant(etatActuel) != unionFind.representant(autreEtat)) {
                    unionFind.unir(etatActuel, autreEtat);
                    unionFind.unir(etatActuel^1, autreEtat^1);
                    nbComposantes--;
                }

                enCours.erase(enContact);
                actuel = reunion;
            }
            else {
                if (enContact->first.fin > actuel.fin) {
                    actuel.fin = enContact->first.debut;
                }
                else {
                    enCours.erase(enContact);
                }
            }

            enContact = enCours.lower_bound(make_pair(actuel, etatActuel));
        }

        enCours.insert( make_pair(actuel, etatActuel) );
    }

    return getPuissance(nbComposantes);
}


int main ()
{
    scanf("%d", &nbObjets);

    for (int iObjet=0; iObjet<nbObjets; iObjet++) {
        scanf("%d %d", &intervalles[iObjet].debut, &intervalles[iObjet].fin);
    }

    printf("%d\n", getNbPossibilites());

    return 0;
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:225:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &nbObjets);
     ~~~~~^~~~~~~~~~~~~~~~~
port_facility.cpp:228:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &intervalles[iObjet].debut, &intervalles[iObjet].fin);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 56 / 56
• Subtask 4: 22 / 22