Submission #1105659

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105659		vladilius	Port Facility (JOI17_port_facility)	C++17	0 / 100	1 ms	336 KiB

port_facility

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
const int mod = 1e9 + 7;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n; cin>>n;
    vector<int> a(n + 1), b(n + 1);
    for (int i = 1; i <= n; i++){
        cin>>a[i]>>b[i];
    }
    
    vector<bool> used(n + 1), t(n + 1);
    queue<int> q;
    vector<int> all;
    int out = 1;
    for (int i = 1; i <= n; i++){
        if (used[i]) continue;
        
        q.push(i);
        used[i] = t[i] = 1;
        
        while (!q.empty()){
            int j = q.front(); q.pop();
            
            for (int k = 1; k <= n; k++){
                if (used[k]) continue;
                if (a[j] < a[k]){
                    if (a[k] < b[j] && b[j] < b[k]){
                        all.pb(k);
                    }
                }
                else {
                    if (a[j] < b[k] && b[k] < b[j]){
                        all.pb(k);
                    }
                }
            }
            for (int k: all){
                used[k] = 1;
                t[k] = !t[j];
                q.push(k);
            }
            all.clear();
        }
        
        out = (out * 2) % mod;
    }
    
    vector<pii> st[2 * n + 2];
    for (int i = 1; i <= n; i++){
        st[a[i]].pb({i, 1});
        st[b[i] + 1].pb({i, 0});
    }
    
    vector<int> s[2];
    for (int i = 1; i <= 2 * n; i++){
        for (auto [j, b]: st[i]){
            if (b){
                s[t[j]].pb(j);
            }
            else {
                if (s[t[j]].back() != j){
                    out = 0;
                    break;
                }
                s[t[j]].pop_back();
            }
        }
    }
    
    cout<<out<<"\n";
}

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