Submission #167014

#	Time	Username	Problem	Language	Result	Execution time	Memory
167014		egekabas	Port Facility (JOI17_port_facility)	C++14	0 / 100	2 ms	376 KiB

port_facility

#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long   ll;
typedef unsigned long long   ull;
typedef long double ld;
typedef pair<ll, ll>    pll;
typedef pair<ull, ull>    pull;
typedef pair<int, int>  pii;
typedef pair<ld, ld>  pld;
ll n;
pll ar[1000009];
ll mod = 1e9+7;
ll prt[1000009];
ll find(ll x){
    if(prt[x] == x)
        return x;
    return prt[x] = find(prt[x]);
}
ll merge(ll x, ll y){
    x = find(x);
    y = find(y);
    prt[x] = y;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    
    cin >> n;
    for(ll i = 0; i < n; ++i){
        cin >> ar[i].ff >> ar[i].ss;
        prt[i] = i;
    }
    sort(ar, ar+n);
    set<pll> s;
    for(ll i = 0; i < n; ++i){
        while(s.size() > 0){
            auto it = s.begin();
            if((*it).ff < ar[i].ff)
                s.erase(it);
            else
                break;
        }
        auto it = s.upper_bound({ar[i].ss, 0});
        if(it == s.begin()){
            s.insert({ar[i].ss, i});
            continue;
        }
        --it;
        if(it == s.begin()){
            merge((*it).ss, i);
            s.insert({ar[i].ss, i});
            continue;
        }
        else{
            cout << "0\n";
            return 0;
        }
    }
    set<int> s2;
    for(ll i = 0; i < n; ++i)
        s2.insert(find(i));
    cout << (1<<(s2.size())) << "\n";
}

Compilation message (stderr)

port_facility.cpp: In function 'll merge(ll, ll)':
port_facility.cpp:27:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

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