루미 알고리즘

#1402플래티넘T-shirts

PO 2016 훈련 캠프코딩출제 Bjarki Ágúst Guðmundsson영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

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].

Example

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.

Task

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 ≤ i < N) is the smallest size the i:th contestant can wear.
  • H: an array with N integers. H[i] (0 ≤ i < N) is the largest size the i:th contestant can wear.
  • T: an array with N integers. T[i] (0 ≤ i < N) is the size of the i:th t-shirt.
  • 0 ≤ L[i] ≤ H[i] ≤ 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 http://progolymp.se/uploads/kattis-attachments/tshirts.zip.

Subtasks

The problem consists of a number of subtasks. Each subtask gives some amount of points, and to pass the subtask you must pass all the test cases in the subtask.

SubtaskPointsLimits
171 ≤ N ≤ 10, 0 ≤ T[i] ≤ 1000
2241 ≤ N ≤ 1000, 0 ≤ T[i] ≤ 1000
3131 ≤ N ≤ 100000, 0 ≤ T[i] ≤ 1
4371 ≤ N ≤ 100000, 0 ≤ T[i] ≤ 100,000
5191 ≤ N ≤ 100000, 0 ≤ T[i] ≤ 10^9

Input format

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]

Output format

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

예제

예제 1

입력
3
3 3 6
7 5 6
4 6 8
출력
2

출처 표기

출처: Programmeringsolympiaden 2016년 훈련 캠프 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.