레이팅 미적용베시는 농부 존의 수익성 좋은 새로운 AI 데이터 센터 사업인 카우위브(CowWeave)에 전력을 공급할 원자로를 설계하고 있다!
원자로 노심은 \(1\)부터 \(N\)까지 번호가 붙은 \(N\) (\(1\le N \le 2\cdot 10^5\))개의 연료봉으로 구성된다. \(i\)번째 연료봉은 "안정 작동 범위" \([l_i, r_i]\) (\(-10^9 \leq l_i \leq r_i \leq 10^9\))를 가지며, 이는 베시가 선택하는 에너지 \(a_i\)가 \(l_i \le a_i \le r_i\)를 만족할 때에만 전력을 생산할 수 있음을 의미한다. 그렇지 않으면 그 연료봉은 가동되지 않고 전력을 생산하지 않는다. 또한 \(a_i\)는 항상 정수여야 한다. \(a_i\)는 \([-10^9, 10^9]\)에 제한되지 않는 임의의 정수일 수 있음에 유의하라.
하지만 연료봉 간의 양자 상호작용으로 인해, 원자로가 멜트다운되는 것을 막기 위해 베시가 \(a_x + a_y = z\) (\(1 \leq x,y \leq N\), \(-10^9\le z\le 10^9\))를 만족시켜야 하는 \((x, y, z)\) 형태의 제약이 \(M\)개 있다.
베시가 멜트다운 없이 설계에서 달성할 수 있는 전력 생산 연료봉의 최대 개수를 찾도록 도와라!
Problem credits: Akshaj Arora
SCORING
- 입력 4: 모든 제약에서 \(x = y\).
- 입력 5-7: 모든 제약에서 \(|x-y|=1\).
- 입력 8-10: 모든 제약에서 \(|x-y|\le 1\).
- 입력 11-13: 추가 조건 없음.
Problem credits: Akshaj Arora
첫째 줄에 독립적인 테스트의 수 \(T\) (\(1\le T\le 10\))가 주어진다. 각 테스트는 다음 형식으로 주어진다.
- 첫째 줄에 두 정수 \(N\)과 \(M\)이 주어진다.
- 둘째 줄에 \(N\)개의 정수 \(l_1, \dots, l_N\)이 주어진다.
- 셋째 줄에 \(N\)개의 정수 \(r_1, \dots, r_N\)이 주어진다.
- 다음 \(M\)개의 줄에 각각 하나의 제약을 나타내는 세 정수 \(x\), \(y\), \(z\)가 주어진다.
모든 테스트에 걸친 \(N\)의 합과 \(M\)의 합이 각각 \(4\cdot 10^5\)를 넘지 않음이 보장된다.
모든 제약을 만족하는 연료봉 에너지 선택이 존재하지 않으면 \(-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
2In the second test, the constraints require that:
- \(a_1 + a_1 = 2\)
- \(a_2 + a_2 = 10\)
Choosing energies \(a=[1, 5, 3]\) results in \(2\) power-generating rods because:
- \(l_1 = 1 \leq a_1 \leq 1 = r_1\)
- \(l_3 = 3 \leq a_3 \leq 3 = r_3\)
and \(a\) satisfies all required constraints.
1
3 2
10 -10 10
10 -10 10
1 2 0
2 3 03Choosing rod energies \(a=[10, -10, 10]\) results in \(3\) power-generating rods.
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 22
-1
1
-1
1riseoj 작성
출처 올림피아드 > USACO > 2025-2026 > First Contest > Silver