Submission #960368

#	Time	Username	Problem	Language	Result	Execution time	Memory
960368		boris_mihov	Port Facility (JOI17_port_facility)	C++17	22 / 100	6096 ms	171200 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 SegmentTree
{
    struct Node
    {
        int sum;
        bool lazy;

        Node()
        {
            sum = lazy = 0;
        }
    
        friend Node operator + (const Node &left, const Node &right)
        {
            Node result;
            result.sum = left.sum + right.sum;
            return result;
        }
    };

    Node tree[8*MAXN];
    void push(int node, int l, int r)
    {
        if (tree[node].lazy == 0)
        {
            return;
        }

        tree[node].sum = r - l + 1;
        if (l < r)
        {
            tree[2*node].lazy = 1;
            tree[2*node + 1].lazy = 1;
        }

        tree[node].lazy = 0;
    }

    void update(int l, int r, int node, int queryL, int queryR)
    {
        push(node, l, r);
        if (queryR < l || r < queryL)
        {
            return;
        }

        if (queryL <= l && r <= queryR)
        {
            tree[node].lazy = 1;
            push(node, l, r);
            return;
        }

        int mid = l + r >> 1;
        update(l, mid, 2*node, queryL, queryR);
        update(mid + 1, r, 2*node + 1, queryL, queryR);
        tree[node] = tree[2*node] + tree[2*node + 1];
    }

    int query(int l, int r, int node, int queryL, int queryR)
    {
        push(node, l, r);
        if (queryL <= l && r <= queryR)
        {
            return tree[node].sum;
        }

        int res = 0;
        int mid = l + r >> 1;
        if (queryL <= mid) res += query(l, mid, 2*node, queryL, queryR);
        if (mid + 1 <= queryR) res += query(mid + 1, r, 2*node + 1, queryL, queryR);
        return res;
    }

    void update(int l, int r)
    {
        update(1, 2 * n, 1, l, r);
    }

    int query(int l, int r)
    {
        return query(1, 2 * n, 1, l, r);
    }
};

int a[MAXN];
int b[MAXN];
int prefix[2 * MAXN];
std::vector <int> g[MAXN];
std::pair <int,int> toSort[MAXN];
SegmentTree partTree[2];

int vis[MAXN];
bool dfs(int node)
{
    for (const int &u : g[node])
    {
        if (vis[u] == vis[node])
        {
            // assert(false);
            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;
    }

    // for (int i = n ; i >= 1 ; --i)
    // {
    //     if (partTree[0].query(b[i], b[i]) && partTree[1].query(b[i], b[i]))
    //     {
    //         std::cout << 0 << '\n';
    //         return;
    //     }

    //     int currentPart = 0;
    //     if (partTree[0].query(b[i], b[i]))
    //     {
    //         currentPart = 1;
    //     }

    //     partTree[currentPart].update(a[i], b[i]);
    //     std::cout << "part: " << a[i] << ' ' << b[i] << " = " << currentPart << '\n';
    // }

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

    int compCnt = 0;
    for (int i = 1 ; i <= n ; ++i)
    {
        if (!vis[i])
        {
            vis[i] = 1;
            if (!dfs(i))
            {
                std::cout << 0 << '\n';
                return;
            }
 
            compCnt++;
        }
    }

    int ans = 1;
    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;
}

Compilation message (stderr)

port_facility.cpp: In member function 'void SegmentTree::update(int, int, int, int, int)':
port_facility.cpp:68:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   68 |         int mid = l + r >> 1;
      |                   ~~^~~
port_facility.cpp: In member function 'int SegmentTree::query(int, int, int, int, int)':
port_facility.cpp:83:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   83 |         int mid = l + r >> 1;
      |                   ~~^~~

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