Submission #171446017 - Codeforces


일단 설명을 하자면

빨간페퍼의 갯수/블랙페퍼의 갯수에 따른 최적값은 정렬해서 풀고 누적합 처리하듯이 풀면 OK -> O(NlgN)


그래서 중요한건 쿼리 처리를 어떻게 하냐는건데

일단 쿼리 중복은 없는거로 가정할게 (실제로 중복은 있는데, 그거 지우고 다시 추가해주는데 O(MlgM))


쿼리 입력에서 (a,b)에 대해서 a가 크면 (a, ), (2a, ), ... 해서 전부다 확인하고

그게 아니면 (,b), (,2b), .. 해서 전부 확인해

최악의 경우에 (1,1), (2,1), (1,2), (3,1) .. 이런식으로 가능한 작은값을 줘도

max(a,b) = k인 쿼리는 많아야 O(k)개임

그래서 중복이 없으면, max=1, max=2, max=3.... 이런것들 먼저 쫙 채우면

결국에 많아야 O(NsqrtM)의 값들을 검사하면 됨


근데 O(NlgN + MlgM + NsqrtM) 이거 무거워서 TLE가 나와 (3초면 통과하는데, 2초에서 아주 조금 모자른거같아)


이제 여기서부터 복잡도가 어떻게 변하는지 모르겠어

사실 (a, N-a), (2a, N-2a), ... 이거 검사를 전부 할 필요가 없어

1. N에 대해서 모든 결과 찾은 값은 convex하게 결과가 나와서,  다음을 검사했을때 더 작은 결과가 나오면 바로 중단하면 됨 -> 이건 복잡도에 영향을 안주는거같고

*2. 일단 (pa, N-pa)가 존재하는걸 확인했다면, 다음을 p+1을 보는게 아니라, p+lcm(a,b)으로 넘어가도 괜찮음


그래서 일단 가능한 조합을 하나라도 찾았다면, 조금 더 빨리 넘어갈 수 있는데, 여기서 의문인게

1. 그러한 원하는 값이 하나라도 존재하지 않는다면, 결국에 처음부터 끝까지 다 확인은 해야하는데, 그런 조합을 맞추다보면 결국 a,b의 값이 커지고, 그럼 그에 따라 또 빠르게 돌아가

2. lcm 단위로 넘어간다면, 그거 자체로도 복잡도에 차이가 있는지 굉장히 헷갈려



그냥 커팅으로의 의미가 있는건지, 아니면 실제로 복잡도에 차이가 생기는데 굉장히 헷갈리네....