BOJ#18865 이제 다시 시작이다

자력 플1 기분 좋고 ~
사실 처음에 풀면서 골드인 줄 알았고, 실제로 아이디어 자체는 그렇게 어렵지 않다.

세그트리이니만큼 플5이상 보정받고 (응용이니 3~4 이상), 손으로 해야하는 계산이 좀 귀찮긴 했다.

 

쨋든 기분조아져서 풀이 써야지

 

 

 

---

[풀이]

x = 스피커부터 (ex, ey) 까지의 맨해튼 거리라고 하자.

세 개의 세그를 준비해서 x에 대응되는 인덱스에 각각 $1,\space x,\space, x^{2}$에 대한 SUM 연산을 수행하게 하자.

 

ex, ey부터 시작해서 훈련소를 덮는 삼각형의 한 변의 길이는 v-x가 된다.

이제 구간을 4개로 나누어서 생각하자. 훈련소의 가로, 세로 중 짧은 것을 m 긴 것을 M이라 하자.

 

1) v-x ∈ [0, m] <=> x ∈ [v-m, v]

2) v-x ∈ (m, M] <=> x ∈ [v-M, v-m)

3) v-x ∈ (M, M+m] <=> x ∈ [v-M-m, v-M)

4) v-x ∈ (M+m, ) <=> x ∈ [1, v-M-m)

 

이후 경계 중복체크하지 않도록 주의해서 세그먼트 트리 3개를 이용해 이차함수를 표현하면 된다.

 

예를 들어 1번 케이스의 경우

$(v-x)^2 = v^{2}-2vx+x^{2}$ 이므로, 이를 코드로 표현하면 아래와 같다.

 

output += v*v*seg.query(v-m,v) - 2*v*seg1.query(v-m,v) + seg2.query(v-m,v)

다른 경우도 계산이 쪼금 많이 귀찮지만 같은 방식으로 진행하면 된다.

 

---

아주 많이 틀렸는데, 시간초과 이전까지는 세그트리에 대입연산해서 틀렸으며, 탑다운 세그트리로 시간초과 먹은 이후로 바텀업 썼는데, 옛날에 짜두었던 바텀업 코드가 틀려서 (...) 한참 헤맸다.

정답률 60% 넘던 문제였는데, 내 제출 이후로 갑자기 30%대가 되었다 ㅋㅋ 18틀 너무 힘들었다.