頁面無法載入？點擊這裡可能會修復。
Placeholder

#8844
子任務

핵 원자로 1s 1024MB

問題

베시는 농부 존의 수익성 좋은 새로운 AI 데이터 센터 사업인 CowWeave를 가동할 원자력 발전용 원자로를 설계하고 있다!

원자로의 노심에는 N개의 연료봉이 있으며(1 ≤ N ≤ 2×10^5), 1번부터 N번까지 번호가 매겨져 있다. i번째 연료봉은 “안정 동작 범위” [l_i, r_i] (−10^9 ≤ l_i ≤ r_i ≤ 10^9)를 가지는데, 이는 베시가 정하는 에너지 a_i가 l_i ≤ a_i ≤ r_i를 만족할 때에만 전력을 생산할 수 있다는 뜻이다. 그렇지 않으면 그 연료봉은 유휴 상태가 되어 전력을 생산하지 않는다. 또한 a_i는 항상 정수여야 한다. a_i는 [−10^9, 10^9] 범위로 제한되지 않으며, 어떤 정수라도 될 수 있음에 유의하라.

하지만 연료봉들 사이의 양자 상호작용 때문에, 원자로가 멜트다운(노심 용융)되지 않도록 베시는 (x, y, z) 형태의 제약 M개를 만족해야 한다. 각 제약은 a_x + a_y = z (1 ≤ x, y ≤ N, −10^9 ≤ z ≤ 10^9) 형태이다.

원자로가 멜트다운되지 않으면서, 전력을 생산하는 연료봉의 개수를 최대 몇 개까지 만들 수 있는지 구하는 일을 도와주어라!


輸入

첫 줄에 독립적인 테스트 개수 T가 주어진다(1 ≤ T ≤ 10). 각 테스트는 다음 형식으로 주어진다.

  • 첫 줄에 정수 N, M이 주어진다.

  • 둘째 줄에 N개의 정수 l_1, …, l_N이 주어진다.

  • 셋째 줄에 N개의 정수 r_1, …, r_N이 주어진다.

  • 다음 M줄에는 각각 세 정수 x, y, z가 주어지며, 각 줄이 하나의 제약을 나타낸다.

모든 테스트를 합쳤을 때 N의 합과 M의 합은 각각 4⋅10^5을 넘지 않음이 보장된다.


輸出

모든 제약을 만족하는 연료봉 에너지의 선택이 아예 존재하지 않으면 −1을 출력하라.

그렇지 않다면, 베시가 얻을 수 있는 전력 생산 연료봉의 최대 개수를 출력하라.


子任務

編號 分數 條件
#110分

모든 제약에 대해 x = y

#220分

모든 제약에 대해 |x − y| = 1

#330分

모든 제약에 대해 |x − y| ≤ 1

#440分

추가 제약 조건 없음


範例 #1

2
3 3
1 2 3
1 2 3
1 1 2
2 2 10
1 1 4
3 2
1 2 3
1 2 3
1 1 2
2 2 10
-1
2

두 번째 테스트에서 제약은 다음을 요구한다:

  • a1 + a1 = 2

  • a2 + a2 = 10

에너지를 a = [1, 5, 3]으로 선택하면, 다음이 성립하므로 전력을 생산하는 연료봉은 2개가 된다:

  • l1 = 1 ≤ a1 ≤ 1 = r1

  • l3 = 3 ≤ a3 ≤ 3 = r3

그리고 a는 모든 요구 제약을 만족한다.


範例 #2

1
3 2
10 -10 10
10 -10 10
1 2 0
2 3 0
3

연료봉 에너지를 a = [10, −10, 10]으로 선택하면 전력을 생산하는 연료봉은 3개가 된다.


範例 #3

5
3 3
1 -1 0
2 1 2
1 2 1
1 3 4
2 3 3
1 1
-100
100
1 1 3
1 1
-100
100
1 1 2
1 2
-100
100
1 1 2
1 1 4
1 2
-100
100
1 1 2
1 1 2
2
-1
1
-1
1

來源

USACO 2026 First Contest, Silver
需要登入才能撰寫程式碼。