[질문] C번 어캐풀죠

[익명(58.124)]

minArr는 그냥 lower_bound로 찾은 값 - arr[i] 하면 되는거 같은데

maxArr는 뒤에서부터 보면서 맵으로 카운팅해야하는거 같은데 맞나요?

[익명(skuld88)]

바로 뒤엣놈의 lower bound가 인덱스가 똑같아서 가로막는 경우만 빼주면돰

[익명(58.124)]

1 2 3 4 1 4 5 6 이면 뒤에 세개는 6-2, 6-3, 6-4 되는거 아닌가요

[익명(skuld88)]

예제중 10 20 30 40은 40의 lower bound가 33을 넘어가니까 이놈이 다른놈이 55를 못쓰게 막는존재임. 그래서 나머지 놈들은 55를 쓸수없음. 이런식으로 방해하는놈들 하나하나 빼주면 끝

[익명(skuld88)]

처리하기 좀 까다로운 반례가 1 2 4 5 -> 1 3 4 5

[익명(58.124)]

둘다 0 1 0 0?

[디피프(dlffff)]

a_i를 빼고 a_i 뒤에 있는 애들을 전부 한칸씩 앞으로 옮기다가 더 못옮기는 순간의 j좌표를 사용해서 미리 전처리

[익명(1.233)]

저도 이렇게 함 ㅇㅇ

[익명(skuld88)]

그리고 이진탐색 안쓰고 그냥 선형탐색으로 됨 정렬이 되어있기 때문에. 이진탐색으로 했으면 높은 확률로 터졌거나 오픈핵에서 터질거임

[익명(58.124)]

분할상환으로 어차피 O(n)인건가? 근데 이진탐색해도 nlogn이라 통과되지않나요?

[익명(14.63)]

n합 < 2*10^5 라서 터지지는 않을거같음

[펜져(penzer27)]

뒤에서 부터 보면서 a -> b 로 갈 수 있는 개수가 같아지면 좁히는 식으로 했음. 다른 사람들이랑 비슷한 듯?

[익명(58.124)]

고를 수 있는 b_i 개수를 전처리로 저장해놓고 a 뒤에서부터 보면서 개수가 같아진다는게 전처리한 값(cnt)가 cnt번 나오면 그 때 인덱스를 줄인다는거죠?

[펜져(penzer27)]

b sort 한 번 전처리 하고, a의 뒤에서 부터 보면서 현재 a[i] 가 갈 수 있는 b_left, b_right 구간을 업데이트 해 나갔음. 그러다가 b_left ~ b_right 구간으로 갈 수 있는 a들의 개수가 b_right - b_left 랑 같아지면 b_right를 당기는 식으로 했음 ㅇㅇ 1대1 매칭이 되기 때문에 이 구간에서는 더 이상 max를 연산 할 수 없으니까.

[펜져(penzer27)]

https://codeforces.com/contest/1721/submission/169865558

[익명(58.124)]

도랏네 왤캐 고수