3001 - 2024_IDS_Spring_Lab8 Scoreboard

Time

2024/04/29 11:00:00 2024/05/06 23:59:00

Clarification

# Problem Asker Description Reply Replier Reply Time For all team

# Problem Pass Rate (passed user / total user)
14314 2024_IDS_Spring_Lab8_Integer_Ordered_Set
14315 2024_IDS_Spring_Lab8_Multiple_Integer_Ordered_Set

14314 - 2024_IDS_Spring_Lab8_Integer_Ordered_Set   

Description

Maintain an integer set, which supports the following operations:

- `I x` : Insert. If x is __NOT__ in the set, insert x into the set. Otherwise, don't do anything. Print the size of the set after finishing the operation.

- `D x` : Delete. If x is in the set, delete x from the integer set. Otherwise, don't do anything. Print the size of the set after finishing the operation.

- `S x` : Search. If x is in the set, print "YES". Otherwise, print "NO".

- `L x` : Lower bound. Print the smallest element __greater than or equal to__ x in the set. If the element doesn't exist, print "$-1$".

- `U x` : Upper bound. Print the smallest element __greater than__ x in the set. If the element doesn't exist, print "$-1$".

There are at least two ways to get AC.

One is to write a binary search tree by yourself. The template below gives the functions of the BST for reference.

Another way is to use std::set<int> and maintain the set by functions in the standard library.

Note: The numbers x in this problem are generated randomly.

Input

The first line is an integer n which is the number of operations.

Following n lines, each line contains one of the operations described above.

Restrictions

- 1 <= n <= 105
- 1 <= x <= 109 for every x in all operations

Testcases 1 and 2:

- only `Insert` and `Search` operations.

Testcases 3 and 4:

- no `Delete` operations.

Testcases 5 ~ 10:

- no further constraints.

Output

For each operation:

- `I x` or `D x` : Print the size of the set after finishing the operation.

- `S x` : If x is in the set, print "YES". Otherwise, print "NO".

- `L x` or `U x` : Print the element if the required element is in the set. Otherwise, print "-1".

Sample Input  Download

Sample Output  Download

Tags




Discuss




14315 - 2024_IDS_Spring_Lab8_Multiple_Integer_Ordered_Set   

Description

Maintain an integer set, which allows more than one identical integer in the set.

The integer set supports the following operations:

- `I x` : Insert. Insert x into the set. Note that you still have to insert the integer even if there exists at least one x in the set. Print the size of the set(number of distinct integers) after finishing the operation.

- `D x` : Delete. If x is in the set, remove one of x from the integer set. If x is not in the set, don't do anything. Print the size of the set(number of distinct integers) after finishing the operation.

- `C x` : Count. Print the occurrence of x in the integer set. If x is not in the set, print "0".

- `L x` : Lower bound. Print the smallest element greater than or equal to x in the set. If the element doesn't exist, print "-1".

- `U x` : Upper bound. Print the smallest element greater than x in the set. If the element doesn't exist, print "-1".

There are at least two ways to get AC.

One is to write a binary search tree by yourself. The template below gives the functions of the BST for reference.

Another way is to use std::map<int, int> and maintain the set by functions in the standard library.

Note: The numbers x in this problem are generated randomly.

Input

The first line is an integer $n$ which is the number of operations.

Following n lines, each line contains one of the operations described above.

Restrictions

- 1 <= n <= 105
- 1 <= x <= 109 for every x in all operations

Output

For each operation:

- `I x` or `D x` : Print the number of distinct integers in the set after finishing the operation.

- `C x` : Print the occurrence of x in the set. If x is not in the set, print "0".

- `L x` or `U x` : Print the element if the required element is in the set. Otherwise, print "-1".

Sample Input  Download

Sample Output  Download

Tags




Discuss