Submission #239309

#	Time	Username	Problem	Language	Result	Execution time	Memory
239309		Coroian_David	Port Facility (JOI17_port_facility)	C++11	100 / 100	2281 ms	247924 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()
{
    //ifstream fin("04-01.txt");
    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];

int CR;

set <pair <int, int>> first[MAX_N + 1][2];

void dfs(int a, int c)
{
    cul[a] = c;
    viz[a] = OP;

    first[CR][c - 1].insert({v[a].yy, a});

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

int TOT;


void delFirst(int c, int x)
{
    first[c][x].erase(*first[c][x].begin());
}

pair <int, int> getFirst(int c, int x)
{

    return *first[c][x].begin();
}

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

    CR = a;

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

    TOT += dim[b];

    if(first[b][0].size() > 0)
        s.erase(getFirst(b, 0));

    if(first[b][1].size() > 0)
        s.erase(getFirst(b, 1));

    first[b][0].clear();
    first[b][1].clear();

    if(first[a][0].size() > 0)
        s.erase(getFirst(a, 0));

    if(first[a][1].size() > 0)
        s.erase(getFirst(a, 1));

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

    if(first[a][0].size() > 0)
        s.insert(getFirst(a, 0));

    if(first[a][1].size() > 0)
        s.insert(getFirst(a, 1));
}

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);

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

        return;
    }

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

int tmp[MAX_N + 1];

void getEdges()
{
    int CATE = 0;
    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;

            int c = getComp((*it).yy);
            int x = cul[(*it).yy] - 1;

            s.erase(it);
            delFirst(c, x);

            if(first[c][x].size() > 0)
                s.insert(getFirst(c, x));
        }

        int k = 0;

        if(s.size() > 0)
        {
            set <pair<int, int>> :: iterator it = s.begin();

            while(it != s.end() && (*it).xx < v[i].yy)
            {
                CATE ++;
                tmp[++ k] = (*it).yy;
                it ++;
            }
        }

        if(k == 0)
        {
            first[i][0].insert({v[i].yy, i});
            s.insert({v[i].yy, i});
        }

        else
        {
            for(int x = 1; x <= k; x ++)
                add(tmp[x], 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: 56 / 56
• Subtask 4: 22 / 22