oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

redpacket Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

redpacket.html

Problem Description

Jianzhi has been packing red packets. To decide on what notes to put in each of the red packets, he has again decided to use his bot, which greedily selects the most valuable note that does not exceed the value he is trying to make, and repeats this process until he achieves his target value.

Jianzhi starts off with N types of notes, with note i having a value of Di dollars. It is guaranteed that no two Di will be the same. He then has to process Q queries.

Each query can be of the form:

  1. 1 x, which adds a new denomination of value x into Jianzhi's set. It is guaranteed that no such denomination already exists in his set.
  2. 2 x, which removes a denomination of value x from Jianzhi's set. It is guaranteed that Jianzhi has such a denomination in his set.
  3. 3 x, which queries how many notes Jianzhi needs to make x dollars, with his bot's algorithm.

Input

The first line of input will contain two integers, N and Q.

The second line of input will contain N integers, with the ith integer representing Di.

The next Q lines of input will contain one query each, in the form stated above.

Output

The output should contain one line for each query of type 3, answering the query. If Jianzhi cannot make the value with his algorithm, output -1 on that line instead.

Limits

For all subtasks: 1 ≤ Di, x ≤ 109.

Subtask 1 (13%): 1 ≤ N, Q ≤ 1000.

Subtask 2 (19%): 1 ≤ N, Q ≤ 300000. There will only be queries of type 3.

Subtask 3 (22%): 1 ≤ N, Q ≤ 300000. There will only be queries of type 1 or 3.

Subtask 4 (46%): 1 ≤ N, Q ≤ 300000.

Subtask 5 (0%): Sample Testcases.

Sample Input 1

Input

3 6
2 3 5
3 8
3 9
1 6
3 9
2 2
3 4

Output

2
-1
2
-1

Tags

Data Structure

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
113201s256MBMinimum
219201s256MBMinimum
322201s256MBMinimum
446801s256MBMinimum
5011s256MBMinimum

Judge Compile Command

g++-8 ans.cpp -o redpacket -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.