Submission #134779

#TimeUsernameProblemLanguageResultExecution timeMemory
134779E869120Port Facility (JOI17_port_facility)C++14
78 / 100
6155 ms817804 KiB
#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;
}

struct FastIO {
	static void scan(double &x) {
		scanf("%lf", &x);
	}
	template <class Integral>
	static void scan(Integral &x) {
		int k, m = 1;
		x = 0;
		for (;;) {
			k = getchar_unlocked();
			//if (k == '-') {
			//	m = -1;
			//	break;
			//}
			//else
			if ('0' <= k && k <= '9') {
				x = k - '0';
				break;
			}
		}
		for (;;) {
			k = getchar_unlocked();
			if (k < '0' || k > '9')
				break;

			x = x * 10 + k - '0';
		}
		//x *= m;//mul is faster than branch-misprediction penalty (maybe)
	}
	template <class Arithmetic, class... Rest>
	static void scan(Arithmetic &x, Rest&... y) {
		scan(x);
		scan(y...);
	}
	static void print(double x, char c) {
		printf("%.12f%c", x, c);
	}
	static void print(const char *x, char c) {
		printf("%s%c", x, c);
	}
	template <class Integral>
	static void print(Integral x, char c) {
		int s = 0, m = 0;
		char f[20];//Is this faster than "static char" ?
		if (x < 0) {
			m = 1;
			x = -x;
		}
		while (x) {
			f[s++] = x % 10;
			x /= 10;
		}

		if (!s)
			f[s++] = 0;

		if (m) putchar_unlocked('-');
		while (s--)
			putchar_unlocked(f[s] + '0');

		putchar_unlocked(c);
	}
	template <class Arithmetic>
	static void println(Arithmetic x) {
		print(x, '\n');
	}
};

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

int main() {
	FastIO::scan(N);
	for (int i = 1; i <= N; i++) {
		FastIO::scan(L[i]);
		FastIO::scan(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:167: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:168: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:180: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:181: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: In instantiation of 'static void FastIO::scan(Integral&) [with Integral = int]':
port_facility.cpp:157:16:   required from here
port_facility.cpp:91:10: warning: unused variable 'm' [-Wunused-variable]
   int k, m = 1;
          ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...