← 返回题目列表

AtCoder · scpc2026_div2_h

H. CUBRID HA 负载平衡

中文机器翻译题面 查看原题

表示言語

/ /

分数: 100 点

问题陈述

CUBRID HA 集群是一个由以下组成的系统 N 服务器。服务器编号从 1 to N.

Jank 已成为 SCSC 的服务器管理员,想要选择 CUBRID HA 集群中的部分服务器来使用。 Jank 打开他选择的服务器并关闭他没有选择的服务器。

统治 SCSC 的 Jank 在打开服务器时选择每个选定的服务器是作为主服务器还是作为从服务器运行。 Master服务器可以处理RW请求和RO请求,Slave服务器可以处理RO请求和SO请求。每台服务器同时最多可以处理一个请求。

如果当前开启的服务器中没有Master服务器,并且当前至少开启了一台Slave服务器,则当前开启的编号最小的Slave服务器立即成为Master服务器。

统治 SCSC 的 Jank 必须处理 Q 按顺序查询以下两种类型。

  • 1 i:关闭服务器 i。如果它已经关闭,请忽略此查询。
  • 2 a b c: a RW 请求, b RO 请求,以及 c SO 请求同时到达。

以类型到达的请求2 查询必须仅使用当前打开的服务器进行处理。每个请求必须分配到一个可以处理该请求的服务器,并且每个服务器最多可以分配一个请求。无法处理在给出查询时未分配的请求。

当所有请求都已分配后,每个服务器都会处理其分配的请求并丢弃已处理的请求。没有剩余请求的服务器准备好再次处理另一个请求。

查找统治 SCSC 的 Jank 最初必须选择的最小服务器数量,以便处理所有请求。如果通过任何方法都无法处理所有请求,则输出 -1 。

约束

  • 1 \leq N,Q \leq 2\,000
  • 1 \leq i \leq N
  • 0 \leq a,b,c \leq N
  • 至少有一个第二类型的查询。
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

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 요청을 처리할 수 있다。 각 서버는 최대 한 개의 요청만 동시에 처리할 수 있다。

만약 현재 켜져 있는 서버 중 Master 서버і 하나도 없고 현재 켜져 있는 Slave 서버і 하나亲爱的大师,我的大师。

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 我想知道我在说什么。 对于字符串 -1을 출력한다.


입력 예 1

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

출력 예 1

3