Submission #928327

#	Time	Username	Problem	Language	Result	Execution time	Memory
928327		boris_mihov	Port Facility (JOI17_port_facility)	C++17	10 / 100	64 ms	134484 KiB

port_facility

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

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

int n;
struct Fenwick
{
    int tree[2 * MAXN];
    void update(int pos, int val)
    {
        for (int idx = pos ; idx <= 2 * n ; idx += idx & (-idx))
        {
            tree[idx] += val;
        }
    }

    int query(int pos)
    {
        int res = 0;
        for (int idx = pos ; idx > 0 ; idx -= idx & (-idx))
        {
            res += tree[idx];
        }

        return res;
    }
};

int a[MAXN];
int b[MAXN];
int cnt[MAXN];
int minA[MAXN];
int maxB[MAXN];
int perm[MAXN];
std::set <int> s;
int prefix[2 * MAXN];
std::pair <int,int> toSort[MAXN];
std::vector <std::pair <int,int>> queries[MAXN];
Fenwick tree;

int vis[MAXN];
std::vector <int> g[MAXN];
bool dfs(int node)
{
    for (const int &u : g[node])
    {
        if (vis[u] == vis[node])
        {
            return false;
        }

        if (vis[u] == 0)
        {
            vis[u] = 3 - vis[node];
            if (!dfs(u)) return false;
        }
    }

    return true;
}

void solve()
{
    std::sort(toSort + 1, toSort + 1 + n);
    for (int i = 1 ; i <= n ; ++i)
    {
        a[i] = toSort[i].first;
        b[i] = toSort[i].second;
        prefix[a[i]]++;
    }

    s.insert(0);
    for (int i = 1 ; i <= n ; ++i)
    {
        auto it = std::prev(s.upper_bound(b[i]));
        maxB[i] = *it;
        s.insert(b[i]);
    }

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

    s.clear();
    s.insert(2 * n + 1);
    for (int i = 1 ; i <= n ; ++i)
    {
        auto it = s.upper_bound(a[perm[i]]);
        minA[perm[i]] = *it;
        s.insert(a[perm[i]]);
    }

    for (int i = 2 ; i < n ; ++i)
    {
        if (maxB[i] > minA[i])
        {
            std::cout << 0 << '\n';
            return;
        }
    }

    for (int i = 1 ; i <= 2 * n ; ++i)
    {
        prefix[i] += prefix[i - 1];
    }

    for (int i = 1 ; i <= n ; ++i)
    {
        queries[i + 1].push_back({b[i], i});
        queries[prefix[b[i]] + 1].push_back({b[i], -i});
    }

    for (int i = n ; i >= 1 ; --i)
    {
        tree.update(b[i], 1);
        for (const auto &[biggerThan, idx] : queries[i])
        {
            int curr = tree.query(2 * n) - tree.query(biggerThan);
            if (idx > 0) cnt[idx] += curr;
            else cnt[-idx] -= curr;
        }
    }

    int sum = 0;
    // for (int i = 1 ; i <= n ; ++i)
    // {
    //     sum += cnt[i];
    // }

    for (int i = 1 ; i <= n ; ++i)
    {
        for (int j = i + 1 ; j <= n ; ++j)
        {
            if (a[j] < b[i] && b[i] < b[j])
            {
                g[i].push_back(j);
                g[j].push_back(i);
                // sum++;
            }
        }
    }

    int compCnt = 0;
    for (int i = 1 ; i <= n ; ++i)
    {
        if (!vis[i])
        {
            vis[i] = 1;
            assert (dfs(i));
            compCnt++;
        }
    }

    int ans = 1;
    assert(sum < n);
    for (int i = 0 ; i < compCnt ; ++i)
    {
        ans <<= 1;
        if (ans >= MOD) ans -= MOD;
    }

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

void input()
{
    std::cin >> n;
    for (int i = 1 ; i <= n ; ++i)
    {
        std::cin >> toSort[i].first >> toSort[i].second;
    }
}

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