Submission #359358

#	Time	Username	Problem	Language	Result	Execution time	Memory
359358		ijxjdjd	Port Facility (JOI17_port_facility)	C++14	0 / 100	1 ms	512 KiB

port_facility

#include <bits/stdc++.h>
#define FR(i, N) for (int i = 0; i < int(N); i++)
using namespace std;

using ll = long long;

const int MAXN = (int)(5e5) + 5;
int main() {
	cin.tie(0);
	cin.sync_with_stdio(0);
	int N;
	cin >> N;
	vector<int> order;
	order.resize(2*N);
	FR(i, N) {
	    int a, b;
	    cin >> a >> b;
	    a--, b--;
	    order[a] = b;
	    order[b] = -a;
	}
	bool zero = false;
	int cnt = 0;
	vector<set<int>> intervals;
	for (int i = 0; i < 2*N; i++) {
        if (order[i] <= 0) {
            intervals.back().erase(intervals.back().find(i));
            if (intervals.back().size() == 0) {
                intervals.pop_back();
                cnt++;
            }
        }
        else {
            if (intervals.size() == 0) {
                intervals.push_back({});
                intervals.back().insert(order[i]);
            }
            else {
                int j = intervals.size()-1;
                intervals.push_back({});
                intervals.back().insert(order[i]);
                int track = 0;
                while (j >= 0 && *intervals[j].begin() <= order[i]) {
                    for (int e : intervals[j]) {
                        if (e <= order[i]) {
                            track++;
                        }
                    }
                    intervals[j].insert(intervals[j+1].begin(), intervals[j+1].end());
                    intervals.pop_back();
                    j--;
                }
//                cout << track << '\n';
                if (track >= 2) {
                    zero = true;
                    break;
                }
            }
        }
	}
	ll tot = !zero;
	ll MOD = (int)(1e9) + 7;
	FR(i, cnt) {
        tot += tot;
        if (tot >= MOD) {
            tot -= MOD;
        }
    }
    cout << tot << '\n';
	return 0;
}

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