Submission #97314

#	Time	Username	Problem	Language	Result	Execution time	Memory
97314		shoemakerjo	Port Facility (JOI17_port_facility)	C++14	0 / 100	2 ms	384 KiB

port_facility

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define pii pair<int, int>

const int maxn = 1000010;
int mod = 1000000007;
int N;

ll ans, inv2;
vector<pii> vals;
set<int> cv; //current ending values

int seg[maxn*8]; //store max incoming in this range

int query(int qs, int qe, int ss = 1, int se = 2*N, int si = 0) {
	if (qs > qe || ss > se || qs > se || qe < ss) return 0;
	if (qs <= ss && se <= qe) return seg[si];

	int mid = (ss+se)/2;
	return max(query(qs, qe, ss, mid, si*2+1),
		query(qs, qe, mid+1, se, si*2+2));
}

void update(int spot, int val, int ss = 1, int se = 2*N, int si = 0) {
	if (ss == se) {
		seg[si] = val;
		return;
	}
	int mid = (ss+se)/2;
	if (spot <= mid) {
		update(spot, val, ss, mid, si*2+1);
	}
	else update(spot, val, mid+1, se, si*2+2);

	seg[si] = max(seg[si*2+1], seg[si*2+2]);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> N;
	ans = 1LL; //good start?
	inv2 = (mod+1)/2LL;

	int a, b;
	for (int i = 0; i < N; i++) {
		cin >> a >> b;
		vals.push_back(pii(a, b));
		update(a, b);
	}
	sort(vals.begin(), vals.end());

	int pb = -1;

	for (pii vp : vals) {
		a = vp.first;
		b = vp.second;

		if (pb != -1) cv.insert(pb);
		pb = b;

		while (cv.size() && *(cv.begin()) < a) {
			// cout << "   thing: " << *(cv.begin()) << endl;
			cv.erase(cv.begin());
		}

		if (cv.size() == 0) {
			// cout << "   option 1 " << endl;
			ans = (ans*2)%mod;

		
			continue;
		}

		auto it = cv.lower_bound(b);

		if (it == cv.begin()) {
			int cur = *it;
			if (query(a+1, b) > cur) {
				// cout << "   option 3 " << endl;
				continue;
			}
			// cout << "   option 2" << endl;
			ans = (ans*2LL)%mod;
		}
		else {
			--it;
			int cur = *it;
			if (query(a+1, cur) > b) {
				// cout << "   option 4 " << endl;
				ans = 0;
			}
			// cout << "   option 5" << endl;
		}
	}
	cout << ans << endl;

}

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