Submission #134814

#	Time	Username	Problem	Language	Result	Execution time	Memory
134814		E869120	Port Facility (JOI17_port_facility)	C++14	78 / 100	6114 ms	498456 KiB

port_facility

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

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

long long datA[1 << 25]; int elA[(1 << 22) + 1], cntA[(1 << 22) + 1];
int AA[1 << 22];
vector<int> IA;
int size_A = 1;

void initA(int sz) {
	while (size_A <= sz) size_A *= 2;
}
void preaddA(int px, int py) {
	px += size_A;
	while (px >= 1) { elA[px]++; px >>= 1; }
}
void calcA() {
	for (int i = 0; i < size_A * 2; i++) cntA[i + 1] = cntA[i] + elA[i];
	for (int i = 0; i < size_A * 2; i++) elA[i] = cntA[i];
	for (int i = 0; i < size_A * 2; i++) AA[i] = elA[i];
}
void addA(int px, int py, int ind) {
	px += size_A; long long r = ((1LL * py) << 20) + 1LL * ind;
	while (px >= 1) {
		datA[cntA[px]] = r; cntA[px]++;
		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] < elA[u + 1] && (datA[AA[u]] >> 20) < x) {
			int pos1 = AA[u];
			int pos2 = lower_bound(datA + elA[u], datA + elA[u + 1], ((1LL * x) << 20)) - datA;
			for (int i = pos1; i < pos2; i++) IA.push_back(datA[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);
}
void queryA(int cl, int cr, int x) {
	// [cl, cr) で x 未満のものを全て push する
	IA.clear();
	query_A(cl, cr, x, 0, size_A, 1);
}

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

long long datB[1 << 25]; int elB[(1 << 22) + 1], cntB[(1 << 22) + 1];
int AB[1 << 22];
vector<int> IB;
int size_B = 1;

void initB(int sz) {
	while (size_B <= sz) size_B *= 2;
}
void preaddB(int px, int py) {
	px += size_B;
	while (px >= 1) { elB[px]++; px >>= 1; }
}
void calcB() {
	for (int i = 0; i < size_B * 2; i++) cntB[i + 1] = cntB[i] + elB[i];
	for (int i = 0; i < size_B * 2; i++) elB[i] = cntB[i];
	for (int i = 0; i < size_B * 2; i++) AB[i] = elB[i];
}
void addB(int px, int py, int ind) {
	px += size_B; long long r = ((1LL * py) << 20) + 1LL * ind;
	while (px >= 1) {
		datB[cntB[px]] = r; cntB[px]++;
		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] < elB[u + 1] && (datB[AB[u]] >> 20) < x) {
			int pos1 = AB[u];
			int pos2 = lower_bound(datB + elB[u], datB + elB[u + 1], ((1LL * x) << 20)) - datB;
			for (int i = pos1; i < pos2; i++) IB.push_back(datB[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);
}
void queryB(int cl, int cr, int x) {
	// [cl, cr) で x 未満のものを全て push する
	IB.clear();
	query_B(cl, cr, x, 0, size_B, 1);
}

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; preaddA(L[id], -R[id]); }
	calcA(); 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; preaddB(R[id], L[id]); }
	calcB(); 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();
			queryA(L[pos], R[pos], -R[pos]);
			queryB(L[pos], R[pos], L[pos]);
			for (int i : IA) { if (col[i] == -1) { col[i] = (col[pos] ^ 1); Q.push(i); } }
			for (int i : IB) { if (col[i] == -1) { col[i] = (col[pos] ^ 1); Q.push(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 function 'int main()':
port_facility.cpp:182: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; preaddA(L[id], -R[id]); }
                                    ~~^~~~~~~~~~~
port_facility.cpp:183:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  calcA(); for (int i = 0; i < A2.size(); i++) { int id = A2[i].second; addA(L[id], -R[id], id); }
                           ~~^~~~~~~~~~~
port_facility.cpp:184: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; preaddB(R[id], L[id]); }
                                    ~~^~~~~~~~~~~
port_facility.cpp:185:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  calcB(); for (int i = 0; i < A1.size(); i++) { int id = A1[i].second; addB(R[id], L[id], id); }
                           ~~^~~~~~~~~~~
port_facility.cpp: In instantiation of 'static void FastIO::scan(Integral&) [with Integral = int]':
port_facility.cpp:172:16:   required from here
port_facility.cpp:106:10: warning: unused variable 'm' [-Wunused-variable]
   int k, m = 1;
          ^

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