Submission #1062838

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062838		Unforgettablepl	Port Facility (JOI17_port_facility)	C++17	100 / 100	2515 ms	206736 KiB

port_facility

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

// #define int long long

const long long modulo = 1e9+7;
const int LIMIT = 1e9;

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    cin >> N;
    vector<pair<int,int>> ships(N);
    for(auto&[a,b]:ships)cin>>a>>b;
    vector<vector<pair<int,int>>> adj(N);
    sort(ships.begin(), ships.end());
    set<pair<int,int>> active;
    set<pair<int,int>> activelightconstrain;
    vector<bool> lightcontrain(N);
    auto helper_remove_until = [&](int x) {
        while(!active.empty() and active.begin()->first<x) {
            auto curr = *active.begin();
            if(lightcontrain[curr.second])activelightconstrain.erase(curr);
            lightcontrain[curr.second]=false;
            active.erase(active.begin());
        }
        if(!active.empty()) {
            auto curr = *active.begin();
            if(lightcontrain[curr.second])activelightconstrain.erase(curr);
            lightcontrain[curr.second]=false;
        }
    };
    auto helper_add = [&](int x) {
        auto iter = active.emplace(ships[x].second,x).first;
        auto iter2 = activelightconstrain.emplace(ships[x].second,x).first;
        lightcontrain[x]=true;
        auto nxt = next(iter);
        if(nxt!=active.end()) {
            lightcontrain[nxt->second]=true;
            activelightconstrain.emplace(*nxt);
        }
        while(activelightconstrain.begin()!=iter2) {
            auto curr = *activelightconstrain.begin();
            auto pre = prev(active.find(curr));
            adj[curr.second].emplace_back(pre->second,0);
            adj[pre->second].emplace_back(curr.second,0);
            lightcontrain[curr.second]=false;
            activelightconstrain.erase(activelightconstrain.begin());
        }
        if(iter==active.begin())return;
        iter = prev(iter);
        adj[iter->second].emplace_back(x,1);
        adj[x].emplace_back(iter->second,1);
    };
    for(int i=0;i<N;i++) {
        auto [a,b] = ships[i];
        helper_remove_until(a);
        helper_add(i);
    }
    long long ans = 1;
    vector visited(N,-1);
    bool works = true;
    function<void(int,int)> dfs = [&](int x,int colour) {
        if(visited[x]!=-1) {
            if(visited[x]!=colour)works=false;
            return;
        }
        visited[x]=colour;
        for(auto&[v,wt]:adj[x])dfs(v,colour^wt);
    };
    for(int i=0;i<N;i++)if(visited[i]==-1){
        ans<<=1;
        ans%=modulo;
        dfs(i,0);
    }
    if(!works)ans=0;
    cout << ans << '\n';
}

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