Submission #1300510

#	Time	Username	Problem	Language	Result	Execution time	Memory
1300510		purplelemon	Port Facility (JOI17_port_facility)	C++20	0 / 100	1 ms	332 KiB

port_facility

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

const int N = 1e6+6, MOD = 1e9+7;
int n;
pair<int,int> nums[N];
int mark[2*N], match[2*N];
set<pair<int,int>> hast, nol, nor;

void solve() {
    cin >> n;
    for (int i = 1;i <= n;i++) {
        cin >> nums[i].first >> nums[i].second;
        mark[nums[i].first] = i;
        mark[nums[i].second] = i;
        match[nums[i].first] = nums[i].second;
        match[nums[i].second] = nums[i].first;
    }
    int e = 0;
    for (int i = 1;i <= 2*n;i++) {
        if (match[i] > i) {
            hast.insert({i,mark[i]});
            nol.insert({i,mark[i]});
            nor.insert({i,mark[i]});
        } else {
            if (nor.find({match[i],mark[i]}) == nor.end()) {
                cout << 0;
                return;
            }
            vector<pair<int,int>> rem;
            for (auto it = nor.lower_bound({match[i],mark[i]});it != nor.end();it++) {
                auto it2 = hast.find(*it);
                int v = it2->second;
                it2++;
                if (it2 != hast.end()) {
                    e++;
                    rem.push_back(*it);
                }
            }
            for (auto val : rem) nor.erase(val);
            rem.clear();
            for (auto it = nol.upper_bound({match[i],mark[i]});it != nol.end();it++) {
                auto it2 = hast.find(*it);
                int v = it2->second;
                if (it2 != hast.begin()) {
                    it2--;
                    e++;
                    rem.push_back(*it);
                }
            }
            for (auto val : rem) nol.erase(val);
            rem.clear();
            auto it = hast.find({match[i],mark[i]});
            it++;
            if (it != hast.end()) {
                nol.insert(*it);
            }
            it--;
            if (it != hast.begin()) {
                it--;
                nor.insert(*it);
            }
            nol.erase({match[i],mark[i]});
            nor.erase({match[i],mark[i]});
            hast.erase({match[i],mark[i]});
        }
    }
    e /= 2;
    e = n-e;
    int ans = 1;
    for (int i = 0;i < e;i++) {
        ans = (ans*2)%MOD;
    }
    cout << ans;
}

int32_t main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
}

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