/ 
Time Limit: 4 sec / Memory Limit: 1024 MB
注意
この問題に対する言及は、2019年12月29日 05:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。
試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。
問題文
あなたは、トレーディングカードを販売しようとしている。 それぞれのカードの種類には 1,...,N の番号がついている。 はじめ、カード i (1 \leqq i \leqq N) の在庫数は C_i 枚である。
あなたは、以下のような Q 件のクエリ S_1, \ldots, S_Q を順番に処理しなければならない。
- 単品販売：カード x を a 枚販売する。ただし、在庫が足りない場合は何もしない。
1 x aという形式で与えられる。 - セット販売：番号が奇数であるカードをそれぞれ a 枚ずつ販売する。ただし、一種類でも在庫が足りない場合は何もしない。
2 aという形式で与えられる。 - 全種類販売：カードを全種類 a 枚ずつ販売する。ただし、一種類でも在庫が足りない場合は何もしない。
3 aという形式で与えられる。
最終的に販売するカードの合計枚数を出力せよ。
制約
- 1 \leqq N \leqq 200,000
- 1 \leqq C_i \leqq 10^9
- 1 \leqq Q \leqq 200,000
- S_i は以下のいずれかの形式の文字列である。
1 x a(1 \leqq x \leqq N かつ 1 \leqq a \leqq 10^9)2 a(1 \leqq a \leqq 10^9)3 a(1 \leqq a \leqq 10^9)
- 入力で与えられる数は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
N C_1 C_2 ... C_N Q S_1 S_2 : S_Q
出力
最終的に販売するカードの合計枚数を出力せよ。
入力例 1
4 5 3 3 5 6 1 2 1 2 2 2 2 3 100 3 1 1 1 3
出力例 1
9
最初、各カードの在庫数はそれぞれ 5,3,3,5 である。 各クエリは以下のように処理される。
- カード 2 を 1 枚販売する。このクエリの後、在庫数は 5,2,3,5 となる。
- カード 1,3 を 2 枚ずつ販売する。このクエリの後、在庫数は 3,2,1,5 となる。
- カード 3 の在庫が足りないため、何もしない。
- 在庫が足りないため、何もしない。
- 全種類のカードを 1 枚ずつ販売する。このクエリの後、在庫数は 2,1,0,4 となる。
- 在庫が足りないため、何もしない。
このように、1,2,5 番目のクエリで 1,4,4 枚のカードを販売し、合計販売枚数は 9 枚となる。
入力例 2
10 241 310 105 738 405 490 158 92 68 20 20 2 252 1 4 36 2 69 1 5 406 3 252 1 3 8 1 10 10 3 11 1 4 703 3 1 2 350 3 10 2 62 2 3 2 274 1 2 1 3 126 1 4 702 3 6 2 174
出力例 2
390
入力例 3
2 3 4 3 1 2 9 2 4 3 4
出力例 3
0
Warning
Do not make any mention of this problem until December 29, 2019, 05:00 a.m. JST. In case of violation, compensation may be demanded.
After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).
Problem Statement
You are going to sell trading cards. You have N kinds of cards, Card 1, \ldots, N, and you have C_i copies of Card i (1 \leq i \leq N) in stock initially.
Now, you have to process Q requests S_1, \ldots, S_Q in order. Each request is in one of the following forms:
- Single Kind: Sell a copies of Card x, or do nothing if you do not have enough copies in stock. Given in the format
1 x a. - Many Kinds: Sell a copies of Card x for every odd number x between 1 and N (inclusive), or do nothing if you do not have enough copies of one or more of those kinds in stock. Given in the format
2 a. - All Kinds: Sell a copies of Card x for every number x between 1 and N, or do nothing if you do not have enough copies of one or more of those kinds in stock. Given in the format
3 a.
Print the total number of cards that will be sold in these requests.
Constraints
- 1 \leq N \leq 200000
- 1 \leq C_i \leq 10^9
- 1 \leq Q \leq 200000
- S_i is a string in one of the following formats:
1 x a(1 \leq x \leq N and 1 \leq a \leq 10^9)2 a(1 \leq a \leq 10^9)3 a(1 \leq a \leq 10^9)
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N C_1 C_2 ... C_N Q S_1 S_2 : S_Q
Output
Print the total number of cards sold in the Q requests.
Sample Input 1
4 5 3 3 5 6 1 2 1 2 2 2 2 3 100 3 1 1 1 3
Sample Output 1
9
Initially, you have 5,3,3,5 copies of Card 1,2,3,4, respectively. Each request will be processed as follows:
- Sell one copy of Card 2. You have now 5,2,3,5 copies of Card 1,2,3,4 in stock.
- Sell two copies of Card 1 and 3 each. You have now 3,2,1,5 copies in stock.
- You do not have enough copies of Card 3 in stock. Do nothing.
- Not enough copies in stock. Do nothing.
- Sell one copy of every kind of card. You have now 2,1,0,4 copies in stock.
- Not enough copies in stock. Do nothing.
As seen above, we will sell 1, 4, 4 cards in the first, second, fifth requests, for a total of 9 cards.
Sample Input 2
10 241 310 105 738 405 490 158 92 68 20 20 2 252 1 4 36 2 69 1 5 406 3 252 1 3 8 1 10 10 3 11 1 4 703 3 1 2 350 3 10 2 62 2 3 2 274 1 2 1 3 126 1 4 702 3 6 2 174
Sample Output 2
390
Sample Input 3
2 3 4 3 1 2 9 2 4 3 4
Sample Output 3
0