제출 #239086

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
239086		Coroian_David	Port Facility (JOI17_port_facility)	C++11	0 / 100	18 ms	23808 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;
}

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

lint rez;

vector <int> g[MAX_N + 1];

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

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

int stk[2][MAX_N + 1];
int stkLen[2];

bitset <MAX_N + 1> viz;
set<pair <int, int>> s;

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);
            add(i, (*it).yy);

            it ++;
        }

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

void dfs(int a)
{
    viz[a] = 1;
    for(auto u : g[a])
    {
        if(viz[u] == 0)
            dfs(u);
    }
}

void getRez()
{
    rez = 1;
    for(int i = 1; i <= n; i ++)
    {
        if(viz[i] == 0)
        {
            rez += rez;
            modd(rez);

            dfs(i);
        }
    }
}

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

    stkLen[0] = stkLen[1] = 1;
    stk[0][1] = stk[1][1] = MOD;

    for(int i = 1; i <= n; i ++)
    {
        for(int h = 0; h <= 1; h ++)
            while(stkLen[h] > 0 && stk[h][stkLen[h]] < v[i].xx)
                stkLen[h] --;

        int poz = (stk[0][stkLen[0]] > v[i].yy && stk[1][stkLen[1]] > v[i].yy ?
                  (stk[0][stkLen[0]] < stk[1][stkLen[1]] ? 0 : 1) :
                  (stk[0][stkLen[0]] > v[i].yy ? 0 : 1));

        if(stk[poz][stkLen[poz]] < v[i].yy)
        {
            rez = 0;
            return;
        }

        stk[poz][++ stkLen[poz]] = v[i].yy;
    }

    getEdges();

    getRez();
}

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

int main()
{
    readFile();

    solve();

    printFile();

    return 0;
}

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