Submission #1216727

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216727		Gray	Port Facility (JOI17_port_facility)	C++20	0 / 100	0 ms	324 KiB

port_facility

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned ll
#define ld long double
#define ff first
#define ss second
#define ln "\n"

const ll MOD = 1e9+7;

void dfs(ll u, vector<ll> &vis, vector<vector<ll>> &A){
    vis[u]=1;
    for (auto v:A[u]){
        if (vis[v]) continue;
        dfs(v, vis, A);
    }
}

void solve(){
    ll n; cin >> n;
    vector<ll> a(2*n+1);
    vector<array<ll, 2>> rng(n);
    for (ll i=0; i<n; i++){
        ll l, r; cin >> l >> r;
        a[l]=i; a[r]=i; rng[i] = {l, r};
    }
    vector<vector<ll>> A(n);
    set<array<ll, 2>> present;
    vector<ll> col(n, -1);
    for (ll i=1; i<=2*n; i++){
        // for (auto ch:present) cout << ch << " ";
        // cout << ln;
        if (!present.count({rng[a[i]][1], a[i]})){
            for (auto [r, ind]:present){
                if (r>rng[a[i]][1]) break;
                if (col[ind]==-1) {
                    if (col[a[i]]==-1){
                        col[ind]=1; col[a[i]]=0;
                    }else col[ind]=col[a[i]]^1;
                }else{
                    if (col[a[i]]==-1) col[a[i]]=col[ind]^1;
                    else if (col[a[i]]==col[ind]){
                        cout << 0 << ln; return;
                    }
                }
                A[ind].push_back(a[i]); A[a[i]].push_back(ind);
            }
            present.insert({rng[a[i]][1], a[i]});
        }else{
            present.erase({rng[a[i]][1], a[i]});
        }
    }
    ll res=1; vector<ll> vis(n);
    for (ll i=0; i<n; i++){
        if (!vis[i]) dfs(i, vis, A), res=(res*2)%MOD;
    }
    cout << res << ln;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(nullptr);
    ll t=1;
    // cin >> t;
    while (t--) solve();
}

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