Submission #369248

#	Time	Username	Problem	Language	Result	Execution time	Memory
369248		fishy15	Port Facility (JOI17_port_facility)	C++14	0 / 100	1 ms	492 KiB

port_facility

#include <iostream>
#include <iomanip>
#include <fstream>
#include <vector>
#include <array>
#include <algorithm>
#include <utility>
#include <map>
#include <queue>
#include <set>
#include <cmath>
#include <cstdio>
#include <cstring>

#define ll long long
#define ld long double
#define eps 1e-8
#define MOD 1000000007

#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3f

// change if necessary
#define MAXN 1000010

using namespace std;

int n;
pair<int, int> pts[MAXN];
int left_inv[2 * MAXN];
int right_inv[2 * MAXN];
int lmost[MAXN];
int rmost[MAXN];

int main() {
    cin.tie(0)->sync_with_stdio(0);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        int a, b; cin >> a >> b;
        pts[i] = {a, b};
        left_inv[a] = i;
        right_inv[b] = i;
    }

    set<int> left, right;
    for (int i = 1; i <= 2 * n; i++) {
        if (left_inv[i]) {
            int c = left_inv[i];
            if (right.empty()) {
                rmost[c] = 0;
            } else {
                auto it = right.lower_bound(pts[c].second);
                if (it == right.begin()) {
                    rmost[c] = 0;
                } else {
                    rmost[c] = *prev(it);
                }
            }
            left.insert(pts[c].first);
            right.insert(pts[c].second);
        } else {
            int c = right_inv[i];
            left.erase(pts[c].first);
            right.erase(pts[c].second);
            if (left.empty()) {
                lmost[c] = INF;
            } else {
                auto it = left.upper_bound(pts[c].first);
                if (it == left.end()) {
                    lmost[c] = INF;
                } else {
                    lmost[c] = *it;
                }
            }
        }
    }


    for (int i = 1; i <= n; i++) {
        if (lmost[i] < rmost[i]) {
            cout << "0\n";
            return 0;
        }
    }

    vector<int> stack;
    int ans_p = n;
    for (int i = 1; i <= 2 * n; i++) {
        if (left_inv[i]) {
            stack.push_back(left_inv[i]);
        } else {
            auto it = find(stack.begin(), stack.end(), right_inv[i]);
            ans_p -= stack.end() - it - 1;
            stack.erase(it);
        }
    }

    ll ans = 1;
    for (int i = 0; i < ans_p; i++) {
        ans += ans;
        if (ans >= MOD) ans -= MOD;
    }

    cout << ans << '\n';

    return 0;
}

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