Submission #656193

#	Time	Username	Problem	Language	Result	Execution time	Memory
656193		ilia_rr	Port Facility (JOI17_port_facility)	C++17	22 / 100	2286 ms	1048576 KiB

port_facility

// بِسْمِ اللَّهِ الرَّحْمَنِ الرَّحِيمِ
// Written by Ilia Rahbar

// #pragma GCC optimize ("O3,no-stack-protector,unroll-loops,fast-math")
// #pragma GCC target ("abm,bmi,bmi2,tbm,avx2")

#include <bits/stdc++.h>
using namespace std;

#define int int64_t
#define ai(x) array <int, x>
#define F first 
#define S second

const int MOD = 1e9 + 7, N = 1e5 + 100;

ai(2) a[N];

int n, d[N], l[N * 2], vs[N], c, ans = 1;

set <int> s;

set <int> :: iterator itr;

vector <int> v[N];

void dfs(int inx)
{
    for (auto i : v[inx])
    {
        if (d[i])
        {
            if (d[i] != 3 - d[inx])
            {
                cout << 0;

                exit(0);
            }

            continue;
        }

        d[i] = 3 - d[inx];

        dfs(i);
    }
}

int32_t main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    cin >> n;

    for (int i = 0; i < n; i++)
       cin >> a[i][0] >> a[i][1]; 

    sort(a, a+n);

    for (int i = 0; i < n; i++)
    {
        l[a[i][0]] = i+1;
        l[a[i][1]] = i+1;
    }

    for (int i = 1; i <= n * 2; i++)
    {
        if (vs[l[i]])
        {
            s.erase(l[i]);

            itr = s.end();

            while (s.size())
            {
                itr--;

                if (*itr < l[i])
                    break;

                v[*itr].push_back(l[i]);
                v[l[i]].push_back(*itr);

                if (itr == s.begin())
                    break;
            }
        }

        else
        {
            vs[l[i]] = 1;

            s.insert(l[i]);
        }
    }

    for (int i = 1; i <= n; i++)
    {
        if (!d[i])
        {
            d[i] = 1;

            dfs(i);

            c++;
        }
    }
    
    for (int i = 0; i < c; i++)
        ans = (ans * 2) % MOD;

    cout << ans;
}

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