Submission #656216

#	Time	Username	Problem	Language	Result	Execution time	Memory
656216		ilia_rr	Port Facility (JOI17_port_facility)	C++17	78 / 100	5379 ms	12956 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, l[N * 2], vs[N], ans = 1, cv[N];

struct DSU
{
    vector <int> v[N];

    int t[N];
    
    bool d[N];

    DSU(int x)
    {
        for (int i = 1; i <= x; i++)
        {
            v[i].push_back(i);
                
            t[i] = i;

            d[i] = 0;
        }
    }

    bool mr(int x, int y)
    {
        if (t[x] == t[y])
        {
            if (d[x] == d[y])
            {
                cout << 0;

                exit(0);
            }

            return 0;
        }

        if (v[t[x]].size() < v[t[y]].size())
            swap(x, y);

        bool nt = (d[x] == d[y]);

        for (auto i : v[t[y]])
        {
            t[i] = t[x];

            v[t[x]].push_back(i);

            if (nt)
                d[i] = !d[i];
        }

        return 1;
    }
};

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

    DSU d(n);

    for (int i = 1; i <= n * 2; i++)
    {
        if (vs[l[i]])
        {
            for (int j = n; j > l[i]; j--)
            {
                if (vs[j] == 1)
                {
                    d.mr(j, l[i]);
                }
            }

            vs[l[i]] = 2;
        }

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

    for (int i = 1; i <= n; i++)
    {
        if (!cv[d.t[i]])
        {
            ans = (ans * 2) % MOD;
            
            cv[d.t[i]] = 1;
        }
    }

    cout << ans;
}

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