Submission #1310948

#TimeUsernameProblemLanguageResultExecution timeMemory
1310948sula2Port Facility (JOI17_port_facility)C++20
0 / 100
0 ms332 KiB
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n; cin >> n;
    vector<int> s[2];
    int l[n+1], r[n+1], event[2*n+1];
    for (int i = 1; i <= n; i++) {
        cin >> l[i] >> r[i];
        event[l[i]] = i;
        event[r[i]] = -i;
    }
    int ans = 1;
    for (int i = 1; i <= 2*n; i++) {
        int ind = abs(event[i]);
        if (event[i] < 0) {
            for (auto& st : s) {
                if (!st.empty() && st.back() == ind) {
                    st.pop_back();
                }
            }
            continue;
        }
        vector<int> opt;
        for (int j = 0; j < 2; j++) {
            if (s[j].empty() || r[ind] < r[s[j].back()]) {
                opt.push_back(j);
            }
        }
        ans = ans*opt.size() % 1'000'000'007;
        if (opt.empty()) {
            cout << 0;
            return 0;
        }
        s[opt[0]].push_back(ind);
    }
    cout << ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...