Submission #131688

#	Time	Username	Problem	Language	Result	Execution time	Memory
131688		imyujin	Port Facility (JOI17_port_facility)	C++14	78 / 100	834 ms	79668 KiB

port_facility

#include <bits/stdc++.h>

using namespace std;

#define MAXN 1000005

typedef int (*Comp)(int, int);
typedef long long lint;

const lint MOD = 1e9 + 7;
int N;
int A[MAXN], B[MAXN];
int mnseg[4 * MAXN], mxseg[4 * MAXN];
int chk[MAXN];
int cnt = -100;

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(idx == 1 && ++cnt < 100) printf("updseg(idx = %d, l = %d, r = %d, x = %d, y = %d)\n", idx, l, r, x, y);
	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]);
	}
	//if(cnt < 100 && cmp(0, 1) == 0) printf("seg[24]**= %d\n", seg[24]);
}

int gseg(int seg[], int idx, int l, int r, int x, int y, Comp cmp) {
	//if(++cnt < 100 && idx == 1) printf("gseg(l = %d, r = %d, x = %d, y = %d, %d)\n", l, r, x, y, cmp(0, 1));
	//if(cnt < 100) printf("seg[%d] = %d\n", idx, seg[idx]);
	if(x <= l && r <= y) return seg[idx];
	if(r < x || y < l) return -1;
	int m = (l + r) / 2;
	//if(cnt < 100 && cmp(0, 1) == 0) printf("seg[24]*= %d\n", seg[24]);
	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) {
	//if(++cnt < 100) printf("findnode(%d)\n", x);
	int t = gseg(mnseg, 1, 1, 2 * N, A[x] + 1, B[x] - 1, mn);
	//if(++cnt < 100) printf("t = %d\n", t);
	if(t != -1 && A[t] < A[x]) return t;
	t = gseg(mxseg, 1, 1, 2 * N, A[x] + 1, B[x] - 1, mx);
	//if(++cnt < 100) printf("t = %d\n", t);
	return (t == -1 || B[t] < B[x]) ? -1 : t;
}

void dfs(int x) {
	//if(++cnt < 100) printf("dfs(%d)\n", x);
	updseg(mnseg, 1, 1, 2 * N, B[x], -1, mn);
	updseg(mxseg, 1, 1, 2 * N, A[x], -1, mx);
	for(int t = findnode(x); t != -1; t = findnode(x)) {
		chk[t] = 3 - chk[x];
		dfs(t);
	}
	//if(++cnt < 100) printf("end dfs(%d)\n", x);
}

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]) {
		//printf("i = %d\n", i);
		chk[i] = 1;
		dfs(i);
		ans = ans * 2 % MOD;
	}

	int cnt = 0;
	for(int i = 0; i < N; i++) if(chk[i] == 1) {
		chk[i] = 0;
		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]) {
		cnt++;
		chk[i] = 1;
		dfs(i);
	}
	for(int i = 0; i < N; i++) if(chk[i] == 2) {
		chk[i] = 0;
		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]) {
		cnt++;
		chk[i] = 2;
		dfs(i);
	}
	
	if(cnt < N) printf("0");
	else printf("%lld", ans);
	return 0;
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:66:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",  &N);
  ~~~~~^~~~~~~~~~~
port_facility.cpp:67: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: 0 / 22