Contest Duration: - (local time) (100 minutes) Back to Home

## B - Intersection Editorial by en_translator

Since $$A_i$$ and $$B_i$$ are between $$1$$ and $$1000$$ (inclusive), $$x$$ should be between $$1$$ and $$1000$$, too.
Therefore, it is sufficient to check for each $$x$$ if it actually satisfies the given $$N$$ conditions.

As another solution, the conditions where $$x$$ should satisfy is equivalent to $$\max(A_1, A_2, A_3, \dots, A_N) \le x\le \min(B_1, B_2, B_3, \dots, B_N)$$, so the answer can be found as $$\max(0, \min(B_1, B_2, B_3, \dots, B_N) - \max(A_1, A_2, A_3, \dots, A_N) + 1)$$.
The complexity of the first solution is $$\Theta (N \max{B_i})$$, while the other is $$\Theta(N)$$, which is faster.

Sample Code (C)

#include <stdio.h>
#include <stdbool.h>

int ri() {
int n;
scanf("%d", &n);
return n;
}

int main() {
int n = ri();
int a[n];
for (int i = 0; i < n; i++) a[i] = ri();
int b[n];
for (int i = 0; i < n; i++) b[i] = ri();

int res = 0;
for (int i = 1; i <= 1000; i++) {
bool ok = true;
for (int j = 0; j < n; j++) if (i < a[j] || i > b[j]) ok = false;
if (ok) res++;
}

printf("%d\n", res);
return 0;
}



Sample Code (Python)

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

res = 0
for i in range(1, 1001) :
ok = True
for j in range(n) :
if i < a[j] or i > b[j] : ok = False
if ok : res += 1

print(res)



posted:
last update: