Submission #602793

#	Time	Username	Problem	Language	Result	Execution time	Memory
602793		elkernos	Port Facility (JOI17_port_facility)	C++17	100 / 100	3020 ms	220520 KiB

port_facility

#include <bits/stdc++.h>

using namespace std;

const int oo = 1e9;

struct treemin {
    typedef pair<int, int> T;
    static constexpr T unit = {oo, oo};
    T f(T a, T b) { return min(a, b); } // (any associative fn)
    vector<T> s;
    int n;
    treemin(int nn = 0, T def = unit) : s(2 * nn, def), n(nn) {}
    void update(int pos, T val)
    {
        for(s[pos += n] = val; pos /= 2;)
            s[pos] = f(s[pos * 2], s[pos * 2 + 1]);
    }
    T query(int b, int e)
    {
        T ra = unit, rb = unit;
        for(b += n, e += n + 1; b < e; b /= 2, e /= 2) {
            if(b % 2) ra = f(ra, s[b++]);
            if(e % 2) rb = f(s[--e], rb);
        }
        return f(ra, rb);
    }
};
struct treemax {
    typedef pair<int, int> T;
    static constexpr T unit = {-oo, -oo};
    T f(T a, T b) { return max(a, b); } // (any associative fn)
    vector<T> s;
    int n;
    treemax(int nn = 0, T def = unit) : s(2 * nn, def), n(nn) {}
    void update(int pos, T val)
    {
        for(s[pos += n] = val; pos /= 2;)
            s[pos] = f(s[pos * 2], s[pos * 2 + 1]);
    }
    T query(int b, int e)
    {
        T ra = unit, rb = unit;
        for(b += n, e += n + 1; b < e; b /= 2, e /= 2) {
            if(b % 2) ra = f(ra, s[b++]);
            if(e % 2) rb = f(s[--e], rb);
        }
        return f(ra, rb);
    }
};

int32_t main()
{
    cin.tie(0)->sync_with_stdio(0);
    int n;
    cin >> n;
    vector<int> a(n + 1), b(n + 1);
    treemin trmin(2 * n + 100);
    treemax trmax(2 * n + 100);
    vector<int> col(n + 1);
    function<void(int, int)> dfs = [&](int i, int c) {
        col[i] = c;
        trmin.update(b[i], {oo, oo});
        trmax.update(a[i], {-oo, -oo});
        while(1) {
            pair<int, int> maybe = trmin.query(a[i] + 1, b[i] - 1);
            if(a[i] < maybe.first) {
                break;
            }
            dfs(maybe.second, 3 - c);
        }
        while(1) {
            pair<int, int> maybe = trmax.query(a[i] + 1, b[i] - 1);
            if(maybe.first < b[i]) {
                break;
            }
            dfs(maybe.second, 3 - c);
        }
    };
    auto check = [&]() {
        vector<vector<int>> st(3);
        vector<pair<int, int>> all;
        for(int i = 1; i <= n; i++) {
            all.push_back({a[i], i});
            all.push_back({b[i], -i});
        }
        sort(all.begin(), all.end());
        for(int i = 0; i < (int)all.size(); i++) {
            int mycol = col[abs(all[i].second)];
            if(all[i].second >= 1) {
                st[mycol].push_back(all[i].second);
            }
            else {
                if(st[mycol].back() != -all[i].second) {
                    return false;
                }
                st[mycol].pop_back();
            }
        }
        return true;
    };
    for(int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i];
        trmin.update(b[i], {a[i], i});
        trmax.update(a[i], {b[i], i});
    }
    const int mod = 1e9 + 7;
    int ans = 1;
    for(int i = 1; i <= n; i++) {
        if(col[i] == 0) {
            ans = (ans * 2) % mod;
            dfs(i, 1);
        }
    }
    cout << (check() ? ans : 0) << '\n';
}

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