Daddy's Journey to Platinum

There is a large hotel, and n customers will arrive soon. Each customer wants to have a single room.

You know each customer's arrival and departure day. Two customers can stay in the same room if the departure day of the first customer is earlier than the arrival day of the second customer.

What is the minimum number of rooms that are needed to accommodate all customers? And how can the rooms be allocated?

The first input line contains an integer n: the number of customers.

Then there are n lines, each of which describes one customer. Each line has two integers a and b: the arrival and departure day.

Print first an integer kk: the minimum number of rooms required.

After that, print a line that contains the room number of each customer in the same order as in the input. The rooms are numbered 1,2,…,k 

3
1 2
2 4
4 4

2
1 2 1

• 1 <= n <= 2x10^5
• 1 <= a <= b <= 10^9

도착일, 출발일과 몇번째 손님인지 저장해서, 도착일 순으로 정렬한다.

출발일과 몇개의 방이 사용중인지 priority queue 에 저장하고, 가장 빠른 출발일과 새로운 도착일을 비교해서 사용중인 방의 수를 변경한다.

There is a street of length x whose positions are numbered 0,1,…,x. Initially, there are no traffic lights, but n sets of traffic lights are added to the street one after another.

Your task is to calculate the length of the longest passage without traffic lights after each addition.

The first input line contains two integers x and n: the length of the street and the number of sets of traffic lights.

Then, the next line contains n integers p_1,p_2,…,p_n : the position of each set of traffic lights. Each position is distinct.

8 3
3 6 2

Print the length of the longest passage without traffic lights after each addition.

5 3 3

• 1 ≤ x ≤ 10^9
• 1 ≤ n ≤2x10^^5
• 0 < p_i < x

입력받은 가로등 위치를 set에 입력하고, 원래 있던 가로등 위치에서 가장 가까운 가로등 위치를 찾아서 간격을 계산한다. 

You have to process n tasks. Each task has a duration and a deadline, and you will process the tasks in some order one after another. Your reward for a task is d−f where d is its deadline and f is your finishing time. (The starting time is 0, and you have to process all tasks even if a task would yield negative reward.)

What is your maximum reward if you act optimally?

The first input line has an integer n: the number of tasks.

After this, there are n lines that describe the tasks. Each line has two integers a and d: the duration and deadline of the task.

Print one integer: the maximum reward.

3
6 10
8 15
5 12

2

• 1 <= n  <= 2x10^5
• 1 <= a,d  <= 10^6

입력받은 업무를 필요 시간을 기준으로 정렬한다.

일은 같이 진행할 수 없기 때문에 전체 업무를 끝내는 시간은 필요 시간 전체의 합으로 고정되어 있으므로, 보상이 큰 일을 먼저 하도록 한다. 필요시간이 짧은 순서로 보상을 계산하기 위해서, 처음부터 진행한 시간과 보상을 기록해서 출력한다.

You are given n cubes in a certain order, and your task is to build towers using them. Whenever two cubes are one on top of the other, the upper cube must be smaller than the lower cube.

You must process the cubes in the given order. You can always either place the cube on top of an existing tower, or begin a new tower. What is the minimum possible number of towers?

The first input line contains an integer n: the number of cubes.

The next line contains n integers k_1,k_2,…,k_n: the sizes of the cubes.

Print one integer: the minimum number of towers.

5
3 8 2 1 5

2

• 1 <= n <= 2x10^5
• 1 <= ki <= 10^9

몇개의 탑이 있고, 그 마지막값이 얼마인지 검색하는 문제이다.

입력받은 블럭의 크기보다 마지막 값이 큰 탑이 있는지 검색하고, 있으면 새로운 블럭 크기로 바꾸고, 없으면 새로운 탑을 만든다. 입력이 끝나면, 탑의 수를 출력한다.

You are given a playlist of a radio station since its establishment. The playlist has a total of n songs.

What is the longest sequence of successive songs where each song is unique?

The first input line contains an integer n: the number of songs.

The next line has n integers k)1,k_2,…,k_n: the id number of each song.

Print the length of the longest sequence of unique songs.

8
1 2 1 3 2 7 4 2

5

• 1 <= n <= 2x10^5
• 1 <= k_i <= 10^9

입력받은 노래 목록을 set에 저장하며 중복목록을 확인한다. 중복목록이 나오면, 중복목록이 나오기 전에 있는 목록들을 지운다. 

노래 목록이 끝나면, set의 크기를 출력한다.

There are n sticks with some lengths. Your task is to modify the sticks so that each stick has the same length.

You can either lengthen and shorten each stick. Both operations cost x where x is the difference between the new and original length.

What is the minimum total cost?

The first input line contains an integer n: the number of sticks.

Then there are n integers: p_1,p_2,…,p_n: the lengths of the sticks.

Print one integer: the minimum total cost.

5
2 3 1 5 2

5

• 1 <= n <= 2x10^5
• 1 <= p_i <= 10^9

입력받은 막대 길이를 정렬하고, median 값을 기준으로 비용을 계산한다.

Given an array of n integers, your task is to find the maximum sum of values in a contiguous, nonempty subarray.

The first input line has an integer n: the size of the array.

The second line has n integers x_1, x_2,…,x_n: the array values.

Print one integer: the maximum subarray sum.

8
-1 3 -2 5 3 -5 2 2

9

• 1 <= n <= 2x10^5
• −10^9 <= x_i <= 10^9

배열에 값을 읽어들이면서, 부분합(1~ k) 을 기록한다.

새로운 배열값과 부분합을 비교해서 최대값을 기록한다.

You are given an array of n integers, and your task is to find two values (at distinct positions) whose sum is x.

The first input line has two integers n and x: the array size and the target sum.

The second line has n integers a_1,a_2,…,a_n : the array values.

Print two integers: the positions of the values. If there are several solutions, you may print any of them. If there are no solutions, print IMPOSSIBLE.

4 8
2 7 5 1

2 4

• 1 <= n <= 2x10^5
• 1 <= x, a_i <= 10^9

입력받은 문자열의 값과 위치를 저장하고, 값을 기준으로 정렬한다.

양쪽에서 출발해서 맞는 값을 찾는다.

작은 값(left)과 큰 값(right)을 더해서 원하는 값과 비교해서 작으면 (left++), 값이 더 크면 (right--) 진행한다.  

답이 있는면 위치를 출력하고,  해당하는 값이 없는 경우 IMPOSSIBLE 출력한다.

You are given the arrival and leaving times of n customers in a restaurant.

What was the maximum number of customers?

The first input line has an integer n: the number of customers.

After this, there are n lines that describe the customers. Each line has two integers a and b: the arrival and leaving times of a customer.

You may assume that all arrival and leaving times are distinct.

Print one integer: the maximum number of customers.

3
5 8
2 4
3 9

2

• 1 <= n <= 2x10^5
• 1 <= a < b <= 10^9

입력받은 시간들을 priority queue 에 저장한다.

단, 먼저 도착한 사람이 앞쪽에 나오도록 모두 음수로 만든다.

저장된 queue 의 제일 위쪽에 있는 자료를 확인해서, 도착 시간이면 +1, 떠난 시간이면 -1을 누적한다.

이렇게 누적한 손님 수중에서 가장 큰 값을 출력한다.

There are n concert tickets available, each with a certain price. Then, m customers arrive, one after another.

Each customer announces the maximum price he or she is willing to pay for a ticket, and after this, they will get a ticket with the nearest possible price such that it does not exceed the maximum price.

The first input line contains integers n and m: the number of tickets and the number of customers.

The next line contains n integers h_1,h_2,…,h_n: the price of each ticket.

The last line contains mm integers t_1,t_2,…,t_m: the maximum price for each customer.

Print, for each customer, the price that they will pay for their ticket. After this, the ticket cannot be purchased again.

5 3
5 3 7 8 5
4 8 3

If a customer cannot get any ticket, print −1.

3
8
-1

• 1 <= n,m <= 2x10^5
• 1 <= h_i, t_i <= 10^9

티켓 가격을 multiset에 저장하고, 희망 가격으로 lower_bound를 찾는다.

그 가격보다 낮은 가격이 있으면 출력하고, 없으면 -1을 출력한다.