Submission #1297362

#TimeUsernameProblemLanguageResultExecution timeMemory
1297362khoile08Port Facility (JOI17_port_facility)C++20
22 / 100
6090 ms6076 KiB
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FOD(i, a, b) for(int i = a; i >= b; i--)
#define fi first
#define se second
#define ll long long
#define ii pair<int,int>
#define pb push_back

const ll INF = 1e18;
const int inf = 1e9;
const int N = 1e6 + 4;
const int mod = 1e9 + 7;

int mul(int a, int b) {
    return 1LL * a * b % mod;
}

int n;
ii a[N];

struct Dsu {
    int cc;
    int root[N], sze[N], h[N];

    void init() {
        cc = n;
        FOR(i, 1, n) {
            h[i] = 0;
            root[i] = i;
            sze[i] = 1;

        }
    }

    ii anc(int u) {
        if(u == root[u]) return {u, 0};
        ii tmp = anc(root[u]);
        root[u] = tmp.fi;
        h[u] += tmp.se;
        return {root[u], h[u]};
    }

    bool join(int u, int v) {
        ii ru = anc(u);
        ii rv = anc(v);
        if(ru.fi == rv.fi) {
            if((ru.se + rv.se) % 2 == 0) return true;
            return false;
        }
        cc--;
        if(sze[ru.fi] < sze[rv.fi]) swap(ru, rv);
        root[rv.fi] = ru.fi;
        sze[ru.fi] += sze[rv.fi];
        h[rv.fi] = (rv.se + ru.se + 1) % 2;
        return false;
    }
} dsu;

vector<int> cur;
int idx[2 * N];

struct Event {
    int p, t, id;
    bool operator < (const Event &b) const {
        return p < b.p;
    }
};
vector<Event> ev;

int binpow(int a, int b) {
    if(b == 0) return 1;
    int tmp = binpow(a, b / 2);
    if(b & 1) return mul(mul(tmp, tmp), a);
    return mul(tmp, tmp);
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n;
    FOR(i, 1, n) {
         cin >> a[i].fi >> a[i].se;
         idx[a[i].fi] = i;
    }

    FOR(i, 1, n) {
        ev.pb({a[i].fi, 0, i});
        ev.pb({a[i].se, 1, i});
    }
    sort(ev.begin(), ev.end());

    dsu.init();
    for(auto x : ev) {
        if(x.t == 0) cur.pb(x.p);
        else {
            vector<int>::iterator it = lower_bound(cur.begin(), cur.end(), a[x.id].fi);
            int st = it - cur.begin() + 1;
            for(; st < cur.size(); st++) {
                if(dsu.join(idx[cur[st]], x.id)) {
                    cout << 0 << '\n';
                    return 0;
                }
            }
            cur.erase(it);
        }
    }

    cout << binpow(2, dsu.cc) << '\n';
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...