Submission #131821

#	Time	Username	Problem	Language	Result	Execution time	Memory
131821		imyujin	Port Facility (JOI17_port_facility)	C++14	100 / 100	5657 ms	143608 KiB

port_facility

#include <bits/stdc++.h>

using namespace std;

#define MAXN 1000005
#define fi first
#define se second

typedef int (*Comp)(int, int);
typedef long long lint;
typedef pair<int, int> pii;

const lint MOD = 1e9 + 7;
int N;
int A[MAXN], B[MAXN];
int mnseg[8 * MAXN], mxseg[8 * MAXN];
int chk[2 * MAXN];

int mn(int a, int b) { return (b == -1 || (a != -1 && A[a] < A[b])) ? a : b; }
int mx(int a, int b) { return (b == -1 || (a != -1 && B[a] > B[b])) ? a : b; }

void updseg(int seg[], int idx, int l, int r, int x, int y, Comp cmp) {
	if(l == r) seg[idx] = y;
	else {
		int m = (l + r) / 2;
		if(x <= m) updseg(seg, idx * 2, l, m, x, y, cmp);
		else updseg(seg, idx * 2 + 1, m + 1, r, x, y, cmp);
		seg[idx] = cmp(seg[idx * 2], seg[idx * 2 + 1]);
	}
}

int gseg(int seg[], int idx, int l, int r, int x, int y, Comp cmp) {
	if(x <= l && r <= y) return seg[idx];
	if(r < x || y < l) return -1;
	int m = (l + r) / 2;
	return cmp(gseg(seg, idx * 2, l, m, x, y, cmp), gseg(seg, idx * 2 + 1, m + 1, r, x, y, cmp));
}

int findnode(int x, bool b) {
	int t;
	if(b) {
		t = gseg(mnseg, 1, 1, 2 * N, A[x] + 1, B[x] - 1, mn);
		if(t != -1 && A[t] < A[x]) return t;
	}
	t = gseg(mxseg, 1, 1, 2 * N, A[x] + 1, B[x] - 1, mx);
	return (t == -1 || B[t] < B[x]) ? -1 : t;
}

void dfs(int x) {
	updseg(mnseg, 1, 1, 2 * N, B[x], -1, mn);
	updseg(mxseg, 1, 1, 2 * N, A[x], -1, mx);
	bool b = true;
	for(int t = findnode(x, b); t != -1; t = findnode(x, b)) {
		if(A[t] > A[x]) b = false;
		chk[t] = 3 - chk[x];
		dfs(t);
	}
}

int main() {
	lint ans = 1ll;

	scanf("%d",  &N);
	for(int i = 0; i < N; i++) scanf("%d%d", A + i, B + i);

	for(int i = 1; i < 8 * N; i++) mnseg[i] = mxseg[i] = -1;
	for(int i = 0; i < N; i++) {
		updseg(mnseg, 1, 1, 2 * N, B[i], i, mn);
		updseg(mxseg, 1, 1, 2 * N, A[i], i, mx);
	}

	for(int i = 0; i < N; i++) if(!chk[i]) {
		chk[i] = 1;
		dfs(i);
		ans = ans * 2 % MOD;
	}

	vector<pii> s;
	for(int i = 0; i < N; i++) {
		s.push_back(make_pair(A[i], i));
		s.push_back(make_pair(B[i], i));
	}
	sort(s.begin(), s.end());

	vector<int> st[2];
	for(auto a : s) {
		if(A[a.se] == a.fi) st[chk[a.se] - 1].push_back(a.se);
		else {
			if(st[chk[a.se] - 1].back() != a.se) {
				printf("0");
				return 0;
			}
			st[chk[a.se] - 1].pop_back();
		}
	}
	
	printf("%lld", ans);
	return 0;
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:63:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",  &N);
  ~~~~~^~~~~~~~~~~
port_facility.cpp:64:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 0; i < N; i++) scanf("%d%d", A + i, B + i);
                             ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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