Submission #134758

#	Time	Username	Problem	Language	Result	Execution time	Memory
134758		E869120	Port Facility (JOI17_port_facility)	C++14	78 / 100	6126 ms	774468 KiB

port_facility

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

class SegmentTree {
public:
	vector<vector<pair<int, int>>> dat;
	vector<int> A;
	vector<int> I;
	int size_ = 1;

	void init(int sz) {
		while (size_ <= sz) size_ *= 2;
		dat.resize(size_ * 2, vector<pair<int, int>>(0, make_pair(0, 0)));
		A.resize(size_ * 2, 0);
	}
	void add(int px, int py, int ind) {
		px += size_;
		while (px >= 1) {
			dat[px].push_back(make_pair(py, ind));
			px >>= 1;
		}
	}
	void query_(int l, int r, int x, int a, int b, int u) {
		if (l <= a && b <= r) {
			if (A[u] < dat[u].size() && dat[u][A[u]].first < x) {
				int pos1 = A[u];
				int pos2 = lower_bound(dat[u].begin(), dat[u].end(), make_pair(x, 0)) - dat[u].begin();
				for (int i = pos1; i < pos2; i++) I.push_back(dat[u][i].second);
				A[u] = pos2;
			}
			return;
		}
		if (b <= l || r <= a) return;
		query_(l, r, x, a, (a + b) >> 1, u * 2);
		query_(l, r, x, (a + b) >> 1, b, u * 2 + 1);
	}
	vector<int> query(int cl, int cr, int x) {
		// [cl, cr) で x 未満のものを全て push する
		I.clear();
		query_(cl, cr, x, 0, size_, 1);
		return I;
	}
};

int N, L[1 << 20], R[1 << 20], f[1 << 21], col[1 << 20];
vector<pair<int, int>> A1, A2;
SegmentTree Z1, Z2;

int main() {
	scanf("%d", &N);
	for (int i = 1; i <= N; i++) {
		scanf("%d%d", &L[i], &R[i]);
		A1.push_back(make_pair(L[i], i)); f[L[i]] = i;
		A2.push_back(make_pair(R[i], i)); f[R[i]] = -i;
	}
	sort(A1.begin(), A1.end());
	sort(A2.begin(), A2.end()); reverse(A2.begin(), A2.end());

	Z1.init(N * 2 + 1); for (int i = 0; i < A2.size(); i++) { int id = A2[i].second; Z1.add(L[id], -R[id], id); }
	Z2.init(N * 2 + 1); for (int i = 0; i < A1.size(); i++) { int id = A1[i].second; Z2.add(R[id], L[id], id); }

	for (int i = 1; i <= N; i++) { col[i] = -1; }

	queue<int>Q; int cnts = 0;
	for (int t = 1; t <= N; t++) {
		if (col[t] != -1) continue;
		col[t] = 0; Q.push(t); cnts++;
		while (!Q.empty()) {
			int pos = Q.front(); Q.pop();
			vector<int> I1 = Z1.query(L[pos], R[pos], -R[pos]);
			vector<int> I2 = Z2.query(L[pos], R[pos], L[pos]);
			for (int i = 0; i < I1.size(); i++) { if (col[I1[i]] == -1) { col[I1[i]] = (col[pos] ^ 1); Q.push(I1[i]); } }
			for (int i = 0; i < I2.size(); i++) { if (col[I2[i]] == -1) { col[I2[i]] = (col[pos] ^ 1); Q.push(I2[i]); } }
		}
	}

	vector<int> S1, S2; bool flag = false;
	for (int i = 1; i <= 2 * N; i++) {
		int id = abs(f[i]);
		if (f[i] > 0) {
			if (col[id] == 0) S1.push_back(id);
			if (col[id] == 1) S2.push_back(id);
		}
		if (f[i] < 0) {
			if (col[id] == 0) { if (S1.size() == 0 || S1[S1.size() - 1] != id) flag = true; else S1.pop_back(); }
			if (col[id] == 1) { if (S2.size() == 0 || S2[S2.size() - 1] != id) flag = true; else S2.pop_back(); }
		}
	}
	int ans = 1; for (int i = 1; i <= cnts; 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 member function 'void SegmentTree::query_(int, int, int, int, int, int)':
port_facility.cpp:29:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (A[u] < dat[u].size() && dat[u][A[u]].first < x) {
port_facility.cpp: In function 'int main()':
port_facility.cpp:63:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  Z1.init(N * 2 + 1); for (int i = 0; i < A2.size(); i++) { int id = A2[i].second; Z1.add(L[id], -R[id], id); }
                                      ~~^~~~~~~~~~~
port_facility.cpp:64:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  Z2.init(N * 2 + 1); for (int i = 0; i < A1.size(); i++) { int id = A1[i].second; Z2.add(R[id], L[id], id); }
                                      ~~^~~~~~~~~~~
port_facility.cpp:76:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int i = 0; i < I1.size(); i++) { if (col[I1[i]] == -1) { col[I1[i]] = (col[pos] ^ 1); Q.push(I1[i]); } }
                    ~~^~~~~~~~~~~
port_facility.cpp:77:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int i = 0; i < I2.size(); i++) { if (col[I2[i]] == -1) { col[I2[i]] = (col[pos] ^ 1); Q.push(I2[i]); } }
                    ~~^~~~~~~~~~~
port_facility.cpp:54:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
port_facility.cpp:56: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