Submission #134777

#	Time	Username	Problem	Language	Result	Execution time	Memory
134777		E869120	Port Facility (JOI17_port_facility)	C++14	78 / 100	6113 ms	771200 KiB

port_facility

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")

// --------------------------------------- セグ木 A ---------------------------------------

vector<long long> datA[1 << 22];
int AA[1 << 22];
vector<int> IA;
int size_A = 1;

void initA(int sz) {
	while (size_A <= sz) size_A *= 2;
}
void addA(int px, int py, int ind) {
	px += size_A; long long r = ((1LL * py) << 20) + 1LL * ind;
	while (px >= 1) {
		datA[px].push_back(r);
		px >>= 1;
	}
}
void query_A(int l, int r, int x, int a, int b, int u) {
	if (l <= a && b <= r) {
		if (AA[u] < datA[u].size() && (datA[u][AA[u]] >> 20) < x) {
			int pos1 = AA[u];
			int pos2 = lower_bound(datA[u].begin(), datA[u].end(), ((1LL * x) << 20)) - datA[u].begin();
			for (int i = pos1; i < pos2; i++) IA.push_back(datA[u][i] & 1048575LL);
			AA[u] = pos2;
		}
		return;
	}
	if (b <= l || r <= a) return;
	query_A(l, r, x, a, (a + b) >> 1, u * 2);
	query_A(l, r, x, (a + b) >> 1, b, u * 2 + 1);
}
vector<int> queryA(int cl, int cr, int x) {
	// [cl, cr) で x 未満のものを全て push する
	IA.clear();
	query_A(cl, cr, x, 0, size_A, 1);
	return IA;
}

// --------------------------------------- セグ木 B ---------------------------------------

vector<long long> datB[1 << 22];
int AB[1 << 22];
vector<int> IB;
int size_B = 1;

void initB(int sz) {
	while (size_B <= sz) size_B *= 2;
}
void addB(int px, int py, int ind) {
	px += size_B; long long r = ((1LL * py) << 20) + 1LL * ind;
	while (px >= 1) {
		datB[px].push_back(r);
		px >>= 1;
	}
}
void query_B(int l, int r, int x, int a, int b, int u) {
	if (l <= a && b <= r) {
		if (AB[u] < datB[u].size() && (datB[u][AB[u]] >> 20) < x) {
			int pos1 = AB[u];
			int pos2 = lower_bound(datB[u].begin(), datB[u].end(), ((1LL * x) << 20)) - datB[u].begin();
			for (int i = pos1; i < pos2; i++) IB.push_back(datB[u][i] & 1048575LL);
			AB[u] = pos2;
		}
		return;
	}
	if (b <= l || r <= a) return;
	query_B(l, r, x, a, (a + b) >> 1, u * 2);
	query_B(l, r, x, (a + b) >> 1, b, u * 2 + 1);
}
vector<int> queryB(int cl, int cr, int x) {
	// [cl, cr) で x 未満のものを全て push する
	IB.clear();
	query_B(cl, cr, x, 0, size_B, 1);
	return IB;
}

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

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());

	initA(N * 2 + 1); for (int i = 0; i < A2.size(); i++) { int id = A2[i].second; addA(L[id], -R[id], id); }
	initB(N * 2 + 1); for (int i = 0; i < A1.size(); i++) { int id = A1[i].second; addB(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 = queryA(L[pos], R[pos], -R[pos]);
			vector<int> I2 = queryB(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: In function 'void query_A(int, int, int, int, int, int)':
port_facility.cpp:28:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (AA[u] < datA[u].size() && (datA[u][AA[u]] >> 20) < x) {
       ~~~~~~^~~~~~~~~~~~~~~~
port_facility.cpp: In function 'void query_B(int, int, int, int, int, int)':
port_facility.cpp:66:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (AB[u] < datB[u].size() && (datB[u][AB[u]] >> 20) < x) {
       ~~~~~~^~~~~~~~~~~~~~~~
port_facility.cpp: In function 'int main()':
port_facility.cpp:98:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  initA(N * 2 + 1); for (int i = 0; i < A2.size(); i++) { int id = A2[i].second; addA(L[id], -R[id], id); }
                                    ~~^~~~~~~~~~~
port_facility.cpp:99:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  initB(N * 2 + 1); for (int i = 0; i < A1.size(); i++) { int id = A1[i].second; addB(R[id], L[id], id); }
                                    ~~^~~~~~~~~~~
port_facility.cpp:111: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:112: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:89:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
port_facility.cpp:91: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