Submission #239119

#	Time	Username	Problem	Language	Result	Execution time	Memory
239119		Coroian_David	Port Facility (JOI17_port_facility)	C++11	22 / 100	6059 ms	98548 KiB

port_facility

#include <bits/stdc++.h>

#define MAX_N 1000000

#define xx first
#define yy second

using namespace std;

typedef long long lint;

const lint MOD = (lint)(1e9) + 7;

void modd(lint &a)
{
    if(a < 0)
        a += MOD;

    if(a >= MOD)
        a -= MOD;
}

vector <int> g[MAX_N + 1];

void baga(int a, int b)
{
    g[a].push_back(b);
}

int n;
pair <int, int> v[MAX_N + 1];

lint rez;

int comps;
int comp[MAX_N + 1];
int cul[MAX_N + 1];
int dim[MAX_N + 1];

void readFile()
{
    cin >> n;
    comps = n;
    for(int i = 1; i <= n; i ++)
    {
        cin >> v[i].xx >> v[i].yy;
        comp[i] = i;
        cul[i] = 1;
        dim[i] = 1;
    }
}

set<pair <int, int>> s;

int OP;
int viz[MAX_N + 1];

void dfs(int a, int c)
{
    cul[a] = c;
    viz[a] = OP;
    for(auto u : g[a])
    {
        if(viz[u] != OP)
        {
            dfs(u, 3 - c);
        }
    }
}

void uneste(int a, int b, int x, int y)
{
    OP ++;
    if(dim[a] < dim[b])
        swap(a, b);

    dim[a] += dim[b];
    comp[b] = a;

//    cout << " FACEM UNIREA " <<

    dfs(y, 3 - cul[x]);
}

int getComp(int a)
{
    return (comp[a] = (comp[a] == a ? a : getComp(comp[a])));
}

void add(int a, int b)
{
    int ca = getComp(a);
    int cb = getComp(b);

    //cout << "UNIM " << ca << " " << cb << " " << a << " " << b << "\n";

    if(ca == cb)
    {
        if(cul[a] == cul[b])
        {
            cout << "0\n";
            exit(0);
        }

        return;
    }

    comps --;
    uneste(ca, cb, a, b);
}

void getEdges()
{
    for(int i = 1; i <= n; i ++)
    {
        while(s.size() > 0)
        {
            set <pair<int, int>> :: iterator it = s.begin();

            if((*it).xx > v[i].xx)
                break;

            s.erase(it);
        }

        set <pair<int, int>> :: iterator it = s.begin();
        while(it != s.end() && (*it).xx < v[i].yy)
        {
            add((*it).yy, i);
            baga((*it).yy, i);
            baga(i, (*it).yy);

            it ++;
        }

       /* for(int h = 1; h <= n; h ++)
            cout << h << " " << cul[h] << "\n";
        cout << "---||---*\n";*/

        s.insert({v[i].yy, i});
    }
}

void getRez()
{
    rez = 1;
    for(int i = 1; i <= comps; i ++)
    {
        rez += rez;
        modd(rez);
    }
}

void solve()
{
    sort(v + 1, v + n + 1);

    getEdges();

    getRez();
}

void printFile()
{
    cout << rez << "\n";
}

int main()
{
    readFile();

    solve();

    printFile();

    return 0;
}

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