I - CUBRID HA Load Balance Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

表示言語

/ /

Score : 100 points

Problem Statement

A CUBRID HA cluster is a system consisting of N servers. The servers are numbered from 1 to N.

Jank has become the server administrator of SCSC and wants to choose some of the servers in the CUBRID HA cluster to use. Jank turns on the servers he chooses and turns off the servers he does not choose.

Jank, who rules SCSC, chooses whether each chosen server operates as a Master or as a Slave when turning it on. A Master server can process RW requests and RO requests, and a Slave server can process RO requests and SO requests. Each server can process at most one request at the same time.

If there is no Master server among the currently turned-on servers and at least one Slave server is currently turned on, the currently turned-on Slave server with the smallest number immediately becomes a Master server.

Jank, who rules SCSC, must process Q queries of the following two types in order.

  • 1 i: Turn off server i. If it is already turned off, ignore this query.
  • 2 a b c: a RW requests, b RO requests, and c SO requests arrive simultaneously.

The requests that arrive in a type-2 query must all be processed using only the servers that are currently turned on. Each request must be assigned to a server that can process that request, and at most one request can be assigned to each server. A request that is not assigned when the query is given cannot be processed.

When all requests have been assigned, each server processes its assigned request and discards the processed request. A server with no remaining request becomes ready to process another request again.

Find the minimum number of servers Jank, who rules SCSC, must choose initially in order to process all requests. If it is impossible to process all requests by any method, output -1 instead.

Constraints

  • 1 \leq N,Q \leq 2\,000
  • 1 \leq i \leq N
  • 0 \leq a,b,c \leq N
  • There is at least one query of the second type.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N Q
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

Each query is in one of the following two formats:

1 i

2 a b c

Output

Output the minimum number of servers Jank, who rules SCSC, must choose initially in order to process all requests. If it is impossible to process all requests by any method, output -1 instead.

Sample Input 1

3 4
2 2 0 0
1 1
2 0 0 1
2 1 0 1

Sample Output 1

3

表示言語

/ /

Score : 100 points

문제

CUBRID HA 클러스터는 N개의 서버로 구성된 시스템이다. 서버는 1번부터 N번까지 번호가 붙어 있다.

SCSC의 서버 관리자로 취임한 Jank는 CUBRID HA 클러스터의 서버 중 몇 대를 선택해 사용하려고 한다. Jank는 선택한 서버를 켜고 선택하지 않은 서버를 끈다.

SCSC를 지배하는 Jank는 선택한 각 서버를 켤 때 Master 또는 Slave 중 하나를 선택해 작동시킨다. Master 서버는 RW 요청과 RO 요청을 처리할 수 있고, Slave 서버는 RO 요청과 SO 요청을 처리할 수 있다. 각 서버는 최대 한 개의 요청만 동시에 처리할 수 있다.

만약 현재 켜져 있는 서버 중 Master 서버가 하나도 없고 현재 켜져 있는 Slave 서버가 하나 이상 있다면, 그중 번호가 가장 작은 서버가 즉시 Master 서버가 된다.

SCSC를 지배하는 Jank는 아래 두 종류의 쿼리 Q개를 순서대로 처리해야 한다.

  • 1 i: i번 서버를 끈다. 이미 꺼져 있는 서버라면 무시한다.
  • 2 a b c: RW 요청 a개, RO 요청 b개, SO 요청 c개가 동시에 들어온다.

2번 쿼리로 들어온 요청은 현재 켜져 있는 서버만 사용해 모두 처리해야 한다. 각 요청은 요청을 처리할 수 있는 서버에 배정되어야 하며, 하나의 서버에는 최대 한 개의 요청만 배정할 수 있다. 쿼리가 주어질 때 배정하지 못한 요청은 처리할 수 없다.

모든 요청이 배정되면 각 서버는 요청을 처리하고 처리한 요청을 버린다. 남은 요청이 없는 서버는 다시 다른 요청을 처리할 수 있는 상태가 된다.

SCSC를 지배하는 Jank가 모든 요청을 처리할 수 있도록 처음에 선택해야 하는 서버 수의 최솟값을 구하여라. 어떤 방법으로도 모든 요청을 처리할 수 없다면 대신 -1을 출력한다.

제한

  • 1 \leq N,Q \leq 2\,000
  • 1 \leq i \leq N
  • 0 \leq a,b,c \leq N
  • 2번 쿼리가 하나 이상 주어진다.
  • 입력으로 주어지는 수는 모두 정수이다.

입력

입력은 다음 형식으로 표준 입력으로 주어진다.

N Q
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

각 쿼리는 다음 두 형식 중 하나이다.

1 i

2 a b c

출력

SCSC를 지배하는 Jank가 모든 요청을 처리할 수 있도록 처음에 선택해야 하는 서버 수의 최솟값을 출력한다. 어떤 방법으로도 모든 요청을 처리할 수 없다면 대신 -1을 출력한다.

입력 예 1

3 4
2 2 0 0
1 1
2 0 0 1
2 1 0 1

출력 예 1

3

表示言語

/ /

配点 : 100 点

問題文

CUBRID HA クラスタは N 台のサーバからなるシステムです．サーバには 1 番から N 番までの番号が付いています．

SCSC のサーバ管理者に就任した Jank は，CUBRID HA クラスタのサーバのうちいくつかを選んで使おうとしています．Jank は選んだサーバを起動し，選ばないサーバを停止します．

SCSC を支配する Jank は，選んだ各サーバを起動するとき，Master または Slave のどちらとして動作させるかを選びます．Master サーバは RW リクエストと RO リクエストを処理でき，Slave サーバは RO リクエストと SO リクエストを処理できます．各サーバは同時に高々 1 個のリクエストしか処理できません．

現在起動しているサーバの中に Master サーバが 1 台も存在せず，現在起動している Slave サーバが 1 台以上存在する場合，現在起動している Slave サーバのうち番号が最も小さいサーバがただちに Master サーバになります．

SCSC を支配する Jank は，以下の 2 種類のクエリを Q 個，順に処理しなければなりません．

  • 1 i: サーバ i を停止する．すでに停止しているサーバなら無視する．
  • 2 a b c: RW リクエスト a 個，RO リクエスト b 個，SO リクエスト c 個が同時に到着する．

2 番目の形式のクエリで到着したリクエストは，現在起動しているサーバだけを使ってすべて処理しなければなりません．各リクエストは，そのリクエストを処理できるサーバに割り当てる必要があり，1 台のサーバには高々 1 個のリクエストしか割り当てられません．クエリが与えられた時点で割り当てられなかったリクエストは処理できません．

すべてのリクエストが割り当てられると，各サーバはリクエストを処理し，処理したリクエストを破棄します．残っているリクエストがないサーバは，再び他のリクエストを処理できる状態になります．

SCSC を支配する Jank がすべてのリクエストを処理するためには，最初に選ぶ必要があるサーバの最小個数を求めてください．どのような方法でもすべてのリクエストを処理できない場合は，代わりに -1 を出力してください．

制約

  • 1 \leq N,Q \leq 2\,000
  • 1 \leq i \leq N
  • 0 \leq a,b,c \leq N
  • 2 番目の形式のクエリが少なくとも 1 個与えられる
  • 入力される数値はすべて整数

入力

入力は以下の形式で標準入力から与えられる．

N Q
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

各クエリは以下の 2 種類のいずれかの形式で与えられる．

1 i

2 a b c

出力

SCSC を支配する Jank がすべてのリクエストを処理するために最初に選ぶ必要があるサーバの最小個数を出力せよ．どのような方法でもすべてのリクエストを処理できない場合は，代わりに -1 を出力せよ．

入力例 1

3 4
2 2 0 0
1 1
2 0 0 1
2 1 0 1

出力例 1

3