| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 14314 | 2024_IDS_Spring_Lab8_Integer_Ordered_Set |
|
| 14315 | 2024_IDS_Spring_Lab8_Multiple_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
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".