oj.uz

Submission #27775

# Submission time Handle Problem Language Result Execution time Memory
27775 2017-07-14T05:12:24 Z 큐브러버(#1177) Port Facility (JOI17_port_facility) C++14
0 / 100
 0 ms 33184 KB 
#include <cstdio>
#include <cassert>
#include <unordered_set>

using namespace std;

unordered_set<long long> S;

int L[1000001], R[1000001];
int a[2000002];
unsigned long long d[1000001];

int s1[1000001], s2[1000001], s1n, s2n;

unsigned int rnd() {
	static unsigned int x = 1983526071;
	return x = x * 1664525 + 1013904223;
}

int main() {
	unsigned long long t;
	int i, j, k, n, r = 1;
	assert(scanf("%d", &n) == 1);
	assert(1 <= n && n <= 1000000);
	for (i = 1; i <= n; i++) {
		assert(scanf("%d%d", &L[i], &R[i]) == 2);
		assert(1 <= L[i] && L[i] < R[i] && R[i] <= n + n);
		a[L[i]] = i;
		a[R[i]] = -i;
		d[i] = (unsigned long long)rnd() << 32 | rnd();
	}
	s1[s1n] = s2[s2n] = 1e9;
	t = 0;
	S.insert(0);
	for (i = 1; i <= n + n; i++) {
		if (a[i] > 0) {
			t ^= d[a[i]];
			if (s1[s1n] > R[a[i]] && (s1[s1n] < s2[s2n] || s2[s2n] < R[a[i]])) s1[++s1n] = R[a[i]];
			else if (s2[s2n] > R[a[i]]) s2[++s2n] = R[a[i]];
			else {
				puts("0");
				return 0;
			}
		}
		else {
			t ^= d[-a[i]];
			if (s1[s1n] == i) s1n--;
			else s2n--;
		}
		if (S.find(t) != S.end()) r = r * 2 % 1000000007;
		else S.insert(t);
	}
	printf("%d\n", r);
}

Compilation message

port_facility.cpp: In function 'int main()':
port_facility.cpp:22:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j, k, n, r = 1;
         ^
port_facility.cpp:22:12: warning: unused variable 'k' [-Wunused-variable]
  int i, j, k, n, r = 1;
            ^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 33184 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 33184 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 56.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 33184 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 33184 KB Output isn't correct
2 Halted 0 ms 0 KB -