시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 1024 MB 2 1 1 50.000%

문제

During the Programming Olympiad finals, each of the $N$ contestants is always given a t-shirt as is customary. However, the judges are sometimes a bit stressed out with making last minute changes to the problem sets (only changes, mind you -- the judges never wait until the day before the contest to make a problem).

This means that when the judges order the t-shirts, they may not look that carefully on what t-shirt sizes the contestants have. After all, who can distinguish a size XS t-shirt from an XL t-shirt? The judges certainly couldn't, but it appears that the contestants can when they try putting their new t-shirts on. Since the judges never learn to plan properly, this will surely be a problem next year as well. But right now it is your problem.

While each contestant has a preferred size, they can wear t-shirts in an interval of sizes. More specifically, the $i$:th contestant (starting from 0) can wear a t-shirt in any size at least $L[i]$ but at most $H[i]$ (both limits inclusive). Here, each size has been assigned an integer so that a higher integer means a larger size. Your task is to assign t-shirts to the contestants, so that as many contestants as possible will get a t-shirt that he or she can wear. The judges have ordered exactly $N$ t-shirts, and the size of the $i$:th t-shirt is $T[i]$.

예제

There are $N = 3$ contestants. The first contestant can wear t-shirts between sizes $3$ and $7$, the second contestant can wear t-shirts in sizes $3$ to $5$, and the last contestant can only wear a size $6$ t-shirt.

The three t-shirts have sizes $4, 6, 8$. Since nobody can wear the last t-shirt, at most two t-shirts can be assigned to the contestants. This can also be achieved, for example by giving the first t-shirt (size $4$) to the first contestant, and the second t-shirt (size $6$) to the last contestant. Thus the answer is 2.

구현

Your task is to compute the maximum number of contestants who can get a t-shirt that he or she can wear. You should implement the function tshirt(N, L, H, T).

  • tshirt(N, L, H, T) - this function will be called exactly once by the judge.
    • N: an integer - the number of contestants (as well as t-shirts).
    • L: an array with $N$ integers. L[i] ($0 \le i < N$) is the smallest size the $i$:th contestant can wear.
    • H: an array with $N$ integers. H[i] ($0 \le i < N$) is the largest size the $i$:th contestant can wear.
    • T: an array with $N$ integers. T[i] ($0 \le i < N$) is the size of the $i$:th t-shirt.
    • $0 \le L[i] \le H[i] \le \max(T)$
    • The function should return an integer, the maximum number of contestants who can get a t-shirt assigned to them.

A code skeleton containing the function to be implemented, together with a sample grader, can be found at attachments.zip.

입력

The sample judge reads input in the following format:

  • line $1$: N
  • line $2$: L[0] L[1] .. L[N - 1]
  • line $3$: H[0] H[1] .. H[N - 1]
  • line $4$: T[0] T[1] .. T[N - 1]

출력

The judge writes a single line containing the return value of tshirt(N, L, H, T).

제한

  • $1 \le N \le 100\,000$
  • $0 \le T[i] \le 10^9$

예제 입력 1

3
3 3 6
7 5 6
4 6 8

예제 출력 1

2

출처

Olympiad > Swedish Olympiad in Informatics > 2016 > KATT1 A번

  • 문제를 만든 사람: Bjarki Ágúst Guðmundsson

제출할 수 있는 언어

C++17, Java 8, C++14, Java 8 (OpenJDK), Java 11, C++20, Java 15, C++14 (Clang), C++17 (Clang), C++20 (Clang)

채점 및 기타 정보

  • 예제는 채점하지 않는다.