4회 문제풀이 08 / ABC 207 C - Many Segments
ABC 207 C - Many Segments
【문제 개요】
1부터 N까지의 번호가 부여된 N개의 구간이 주어집니다. 구간 i는
- tᵢ = 1라면 [lᵢ, rᵢ]
- tᵢ = 2라면 [lᵢ, rᵢ)
- tᵢ = 3라면 (lᵢ, rᵢ]
- tᵢ = 4라면 (lᵢ, rᵢ) 이다.
1 ≦ i < j ≦ N을 만족하는 정수의 조합 (i, j)중에서 구간 i와 구간 j가 공통부분을 같는것이 몇 개 있습니까? A = (A₁, A₂, …, Aₙ)가 주어집니다. 다음의 조건을 전부 만족하는 정수 조합 (i, j)의 수를 구하시오.
- 1 ≦ i < j ≦ N
- Aᵢ ≠ Aⱼ
※ 구간 [X, Y], [X, Y), (X, Y], (X, Y)란?
- [X, Y]는 X이상, Y이하의 모든 실수로 구성된 구간
- [X, Y)는 X이상, Y미만의 모든 실수로 구성된 구간
- (X, Y]는 X초과, Y이하의 모든 실수로 구성된 구간
- (X, Y)는 X초과, Y미만의 모든 실수로 구성된 구간 즉, []는 포함, ()는 포함하지 않는다는 의미이다(이상이하, 초과미만)
【전제】
- 2 ≦ N ≦ 2000
- 1 ≦ tᵢ ≦ 4
- 1 ≦ lᵢ < rᵢ ≦ 10⁹
- 입력은 모두 정수이다.
【입력 형태】
1
2
3
4
5
N
t₁ l₁ r1
t₂ l₂ r2
...
tₙ lₙ rₙ
【출력 형태】
구간 i와 구간 j가 공통부분을 갖는 정수의 조합 (i, j)의 개수를 출력하시오.
【예시】
입력 예 1
1
2
3
4
3
1 1 2
2 2 3
3 2 4
출력 예 1
1
2
문제의 정의에 따라, 구간 1은 [1, 2], 구간 2는 [2, 3), 구간 3은 (2, 4]입니다. 구간 i와 구간 j가 공통 부분을 갖는 정수의 조합(i, j)는 (1, 2)와 (2, 3)의 2개입니다. 각각 [2, 2]와 (2, 3)를 공통 부분으로 가집니다.
입력 예 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
19
4 210068409 221208102
4 16698200 910945203
4 76268400 259148323
4 370943597 566244098
1 428897569 509621647
4 250946752 823720939
1 642505376 868415584
2 619091266 868230936
2 306543999 654038915
4 486033777 715789416
1 527225177 583184546
2 885292456 900938599
3 264004185 486613484
2 345310564 818091848
1 152544274 521564293
4 13819154 555218434
3 507364086 545932412
4 797872271 935850549
2 415488246 685203817
출력 예 2
1
102
このポストは作成者の CC BY 4.0 ライセンスによって保護されます。