Submission #1297359

#TimeUsernameProblemLanguageResultExecution timeMemory
1297359khoile08Port Facility (JOI17_port_facility)C++20
22 / 100
6091 ms6216 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 db double
#define ii pair<int,int>
#define pb push_back
#define MASK(i) (1LL << i)
#define sq(i) (1LL * (i) * (i))
#define task "task"

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);
}

void solve() {
    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;
                }
            }
            cur.erase(it);
        }
    }

    cout << binpow(2, dsu.cc) << '\n';
}

signed main() {
    if(fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        //freopen(task".out", "w", stdout);
    }
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int tc = 1;
    // cin >> tc;
    while(tc--) {
        cin >> n;
        FOR(i, 1, n) {
             cin >> a[i].fi >> a[i].se;
             idx[a[i].fi] = i;
        }
        solve();
    }
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:111:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...