Submission #1143167

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143167		boris_mihov	Port Facility (JOI17_port_facility)	C++17	10 / 100	27 ms	32072 KiB

port_facility

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <set>

typedef long long llong;
const int MAXN = 1e6 + 10;
const int MOD = 1e9 + 7;
const llong INF = 2e18;
const int MAXLOG = 21;

int n;
struct Fenwick
{
    int tree[2 * MAXN];
    void reset()
    {
        std::fill(tree + 1, tree + 1 + 2 * n, 0);
    }

    void update(int idx, int val)  
    {
        for (; idx <= 2 * n ; idx += idx & (-idx))
        {
            tree[idx] += val;
        }
    }
    
    int query(int idx)
    {
        int res = 0;
        for (; idx ; idx -= idx & (-idx))
        {
            res += tree[idx];
        }

        return res;
    }

    int findKth(int k)
    {
        int idx = 0;
        for (int lg = MAXLOG - 1 ; lg >= 0 ; --lg)
        {
            if (idx + (1 << lg) <= 2 * n && tree[idx + (1 << lg)] < k)
            {
                idx += (1 << lg);
                k -= tree[idx];
            }
        }

        return idx + 1;
    }
};

Fenwick fenwick;
int perm[MAXN];
int l[MAXN];
int r[MAXN];
int maxR[MAXN];
int minL[MAXN];
std::vector <int> g[MAXN];
bool vis[MAXN];

void dfs(int node)
{
    vis[node] = true;
    for (const int &u : g[node])
    {
        if (vis[u])
        {
            continue;
        }

        dfs(u);
    }
}

void solve()
{
    std::iota(perm + 1, perm + 1 + n, 1);
    std::sort(perm + 1, perm + 1 + n, [&](int x, int y)
    {
        return r[x] > r[y];
    });

    minL[0] = 2 * n + 1;
    for (int i = 1 ; i <= n ; ++i)
    {
        int k = fenwick.query(l[perm[i]] - 1) + 1;
        int res = fenwick.findKth(k);

        if (k <= i - 1 && res <= r[perm[i]])
        {
            minL[perm[i]] = res;
        } else
        {
            minL[perm[i]] = 2 * n + 1;
        }

        fenwick.update(l[perm[i]], 1);
    }

    fenwick.reset();
    std::sort(perm + 1, perm + 1 + n, [&](int x, int y)
    {
        return l[x] < l[y];
    });

    for (int i = 1 ; i <= n ; ++i)
    {
        int k = fenwick.query(r[perm[i]]);
        int res = fenwick.findKth(k);

        if (k > 0 && res >= l[perm[i]])
        {
            maxR[perm[i]] = res;
        } else
        {
            maxR[perm[i]] = 0;
        }

        fenwick.update(r[perm[i]], 1);
    }

    for (int i = 1 ; i <= n ; ++i)
    {
        if (minL[i] < maxR[i])
        {
            std::cout << 0 << '\n';
            return;
        }
    }

    for (int i = 1 ; i <= n ; ++i)
    {
        for (int j = i + 1 ; j <= n ; ++j)
        {
            if (l[perm[j]] < r[perm[i]] && r[perm[i]] < r[perm[j]])
            {
                g[i].push_back(j);
                g[j].push_back(i);
            }
        }
    }

    int ans = 1;
    for (int u = 1 ; u <= n ; ++u)
    {
        if (!vis[u])
        {
            dfs(u);
            ans *= 2;
            if (ans >= MOD) ans -= MOD;
        }
    }

    std::cout << ans << '\n';
}

void input()
{
    std::cin >> n;
    for (int i = 1 ; i <= n ; ++i)
    {
        std::cin >> l[i] >> r[i];
    }
}

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIOI();
    input();
    solve();

    return 0;
}

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