Submission #134679

#	Time	Username	Problem	Language	Result	Execution time	Memory
134679		E869120	Port Facility (JOI17_port_facility)	C++14	78 / 100	3420 ms	1048580 KiB

port_facility

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
#pragma warning (disable: 4996)

// 定数
const int MAX_N = (1 << 20);
const int MAX_BLOCK = 22;

// 一般
bool flag = false;
int N, L[MAX_N + 9], R[MAX_N + 9];

// グラフ
int cnts;
int col[MAX_N * MAX_BLOCK + 9], KAISOU;
int m_front[MAX_N * MAX_BLOCK + 9], m_back[MAX_N * MAX_BLOCK + 9];
vector<int> G[MAX_N * MAX_BLOCK + 9];

// セグ木
int SIZE_;
int el[MAX_N * 4 + 9], cnt[MAX_N * 4 + 9], cnt2[MAX_N * 4 + 9], C[MAX_N * 4 + 9];
pair<int, int> dat[MAX_N * MAX_BLOCK + 9];

// キュー
queue<int>Q;

void init() {
	SIZE_ = 1; KAISOU = 1;
	while (SIZE_ <= N * 2) { SIZE_ *= 2; KAISOU++; }

	for (int i = 1; i <= N; i++) {
		int cx = L[i] + SIZE_;
		while (cx >= 1) {
			cnt[cx]++; cx >>= 1;
		}
	}
	for (int i = 0; i < SIZE_ * 2; i++) {
		el[i + 1] = el[i] + cnt[i];
		cnt2[i] = el[i];
	}
}

void precount() {
	for (int i = 1; i < SIZE_ * 2; i++) sort(dat + el[i], dat + el[i + 1]);
	for (int i = 1; i < SIZE_ * 2; i++) C[i] = (1 << 30);
}

void query_(int l, int r, int x, int pos, int a, int b, int u) {
	if (l <= a && b <= r) {
		int pos1 = lower_bound(dat + el[u], dat + el[u + 1], make_pair(x, 0)) - dat;
		if (pos1 < el[u + 1]) {
			int id = dat[pos1].second;
			G[pos].push_back(id);
			G[id].push_back(pos);
		}
		C[u] = min(C[u], x);
		return;
	}
	if (r <= a || b <= l) return;
	query_(l, r, x, pos, a, (a + b) >> 1, u * 2);
	query_(l, r, x, pos, (a + b) >> 1, b, u * 2 + 1);
}

void query(int cl, int cr, int x, int pos) {
	query_(cl, cr, x, pos, 0, SIZE_, 1);
}

void lastcount() {
	for (int i = 1; i < SIZE_ * 2; i++) {
		for (int j = el[i]; j < el[i + 1] - 1; j++) {
			if (C[i] <= dat[j].first) {
				int id1 = dat[j].second;
				int id2 = dat[j + 1].second;
				m_back[id1] = id2;
				m_front[id2] = id1;
			}
		}
	}
}

int main() {
	//FILE *in = freopen("in1.txt", "r", stdin);
	scanf("%d", &N); vector<pair<int, int>> vec1;
	for (int i = 1; i <= N; i++) {
		scanf("%d%d", &L[i], &R[i]);
		//L[i] = i; R[i] = i + N;
		vec1.push_back(make_pair(L[i], R[i]));
	}
	sort(vec1.begin(), vec1.end());
	for (int i = 1; i <= N; i++) { L[i] = vec1[i - 1].first; R[i] = vec1[i - 1].second; }

	init();
	for (int i = 1; i <= N; i++) {
		int cl = SIZE_ + L[i];
		dat[cnt2[cl]].first = R[i];
		dat[cnt2[cl]].second = cnts;
		cnt2[cl]++; cnts++;
		while (cl >= 2) {
			cl >>= 1;
			dat[cnt2[cl]].first = R[i];
			dat[cnt2[cl]].second = cnts;
			cnt2[cl]++;
			cnts++;
		}
	}
	precount();

	for (int i = 1; i <= N; i++) {
		int pos1 = lower_bound(dat + el[1], dat + el[2], make_pair(R[i], 0)) - dat;
		int id = dat[pos1].second;
		query(L[i], R[i] + 1, R[i] + 1, id);
	}

	for (int i = 0; i <= cnts; i++) { m_back[i] = -1; m_front[i] = -1; }
	lastcount();

	for (int i = 0; i <= cnts; i++) col[i] = -1;

	int components = 0;
	for (int i = 0; i < cnts; i++) {
		if (col[i] != -1) continue;

		col[i] = 0; Q.push(i);
		while (!Q.empty()) {
			int pos = Q.front(); Q.pop();
			for (int j : G[pos]) {
				if (col[j] == -1) { col[j] = (col[pos] ^ 1); Q.push(j); }
				else if (col[j] == col[pos]) flag = true;
			}
			if (pos % KAISOU >= 1) {
				if (col[pos - 1] == -1) { col[pos - 1] = col[pos]; Q.push(pos - 1); }
				else if (col[pos - 1] != col[pos]) flag = true;
			}
			if (pos%KAISOU <= KAISOU - 2) {
				if (col[pos + 1] == -1) { col[pos + 1] = col[pos]; Q.push(pos + 1); }
				else if (col[pos + 1] != col[pos]) flag = true;
			}
			if (m_back[pos] >= 0) {
				int j = m_back[pos];
				if (col[j] == -1) { col[j] = col[pos]; Q.push(j); }
				else if (col[j] != col[pos]) flag = true;
			}
			if (m_front[pos] >= 0) {
				int j = m_front[pos];
				if (col[j] == -1) { col[j] = col[pos]; Q.push(j); }
				else if (col[j] != col[pos]) flag = true;
			}
		}
		components++;
	}

	int ans = 1;
	for (int i = 0; i < components; i++) { ans *= 2; ans %= 1000000007; }
	if (flag == true) ans = 0;

	cout << ans << endl;
	return 0;
}

Compilation message (stderr)

port_facility.cpp:6:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning (disable: 4996)
 
port_facility.cpp: In function 'int main()':
port_facility.cpp:86:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N); vector<pair<int, int>> vec1;
  ~~~~~^~~~~~~~~~
port_facility.cpp:88:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &L[i], &R[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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