Submission #103424

#	Time	Username	Problem	Language	Result	Execution time	Memory
103424		szawinis	Port Facility (JOI17_port_facility)	C++17	100 / 100	3225 ms	105976 KiB

port_facility

/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author
 */

#include <bits/stdc++.h>
using namespace std;
#define long long long
const long MOD = 1e9+7, LINF = 1e18 + 1e16;
const int INF = 1e9+1;
const double EPS = 1e-10;
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
const int N = 2e6+1;

struct seg {
    int l, r, i;
    bool operator<(const seg &rhs) const {
        return r < rhs.r;
    }
    seg(int l, int r, int i): l(l), r(r), i(i) {}
};

class PortFacility {

    int n, dsu[N];
    vector<seg> a;
    set<seg> st;

    int root(int v) {
        return (dsu[v] < 0 ? v : dsu[v] = root(dsu[v]));
    }

    void merge(int u, int v) {
        if((u = root(u)) == (v = root(v))) return;
        dsu[u] += dsu[v];
        dsu[v] = u;
    }

public:
    void solve(istream &cin, ostream &cout) {
        cin >> n;
        for(int i = 0, l, r; i < n; i++) {
            cin >> l >> r;
            a.emplace_back(l, r, i);
        }
        sort(a.begin(), a.end(), [] (seg x, seg y) { return x.l < y.l; });

        fill(dsu, dsu+2*n+1, -1);
        for(seg s: a) {
            while(!st.empty() && st.begin()->r < s.l) st.erase(st.begin());
            auto lim = st.upper_bound(seg(-1, s.r, -1));
//            cerr << "main" << s.l << ' ' << s.r << ' ' << s.i << endl;
            for(auto it = st.begin(); it != lim; ++it) {
//                cerr << it->l << ' ' << it->r << ' ' << it->i << endl;
                merge(s.i, it->i + n);
                merge(s.i + n, it->i);
                if(root(it->i) == root(prev(lim)->i)) break;
            }
            st.insert(s);
        }
        int cnt = 0;
        for(int i = 0; i < n; i++) {
            if(root(i) == root(i + n)) {
                cout << 0 << endl;
                return;
            }
            cnt += dsu[i] < 0;
        }
        long ans = 1;
        while(cnt--) ans = (ans <<= 1) % MOD;
        cout << ans << endl;
    }
};

class Solver {
public:
    void solve(std::istream& in, std::ostream& out) {
        PortFacility *obj = new PortFacility();
        obj->solve(in, out);
        delete obj;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    Solver solver;
    std::istream& in(std::cin);
    std::ostream& out(std::cout);
    solver.solve(in, out);
    return 0;
}

Compilation message (stderr)

port_facility.cpp: In member function 'void PortFacility::solve(std::istream&, std::ostream&)':
port_facility.cpp:71:26: warning: operation on 'ans' may be undefined [-Wsequence-point]
         while(cnt--) ans = (ans <<= 1) % MOD;
                      ~~~~^~~~~~~~~~~~~~~~~~~

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