완료 시각 계산
서버 에 지금까지 들어온 마지막 제출의 완료 시각을 라고 하자. 시각 에 채점 시간 인 제출이 서버 에 들어오면 시작 시각과 완료 시각은
이다. 이후 를 새 완료 시각으로 갱신한다. 각 서버가 FIFO 순서로 제출을 처리하므로 실제 큐를 저장할 필요는 없다.
여러 서버가 동시에 동작하므로 제출 쿼리 순서와 실제 완료 순서는 다를 수 있다. 계산한 완료 시각을 기준으로 완료 이벤트를 최소 힙에 저장한다. 시각 의 쿼리를 처리하기 전에 완료 시각이 이하인 이벤트를 모두 꺼내 데이터베이스와 랭킹 자료구조에 반영한다.
완료 시각은 입력의 보다 훨씬 커질 수 있다. 한 서버에 채점 시간 인 제출이 많이 쌓일 수 있으므로 완료 시각은 반드시 64비트 정수로 저장한다.
문제별 랭킹
한 제출의 문제 랭킹 비교 키는
이다.
각 문제에서 필요한 것은 상위 개뿐이다. 따라서 문제마다 현재 상위 개 기록만 정렬된 벡터로 유지한다. 새 완료 기록을 추가하고 정렬한 뒤 원소가 개가 되면 가장 뒤의 원소를 제거한다.
한 번 상위 개에서 밀려난 기록은 이후 더 많은 기록이 추가되더라도 다시 상위 개에 들어올 수 없다. 새 기록의 추가는 기존 기록의 상대 순위를 개선하지 않기 때문이다. 따라서 문제 하나당 개의 기록만 저장하면 된다.
사용자 랭킹
사용자 에 대해 다음 두 값을 저장한다.
사용자 랭킹의 비교 키는
이다. 이 키를 std::set에 저장하면 앞에서부터 랭킹 순서가 된다.
사용자가 새로운 문제를 처음 풀면 기존 키를 집합에서 삭제한다. 그 뒤 를 증가시키고 를 해당 제출의 완료 시각으로 바꾼 다음 새 키를 삽입한다.
같은 사용자가 같은 문제를 여러 번 제출해도 푼 문제 수는 한 번만 증가해야 한다. 완료된 쌍을 해시 집합에 저장하고, 완료 이벤트를 처리할 때 그 쌍이 처음 등장한 경우에만 사용자 랭킹을 갱신한다. 중요한 점은 중복 여부를 제출 시점이 아니라 완료 시점에 판정해야 한다는 것이다. 나중에 제출된 같은 문제의 제출이 다른 서버에서 더 먼저 완료될 수 있기 때문이다.
문제별 랭킹에는 같은 사용자의 같은 문제 제출도 모두 서로 다른 기록으로 추가한다.
쿼리 처리
각 쿼리의 시각을 라고 하자. 먼저 최소 힙에서 완료 시각이 이하인 이벤트를 모두 꺼내 처리한다.
서브태스크
서브태스크 1에서는 매 출력 쿼리마다 지금까지의 완료 제출을 다시 조사하고 정렬해도 된다. 총 가 이하이므로 풀이가 충분하다.
서브태스크 2에서는 서버가 하나이고 번 쿼리가 없다. 완료 순서가 제출 순서와 같으므로 완료 이벤트를 큐로 처리하고 문제별 상위 개만 유지하면 된다.
서브태스크 3에서는 사용자 랭킹이 필요 없다. 여러 서버의 완료 이벤트를 최소 힙으로 처리하고 문제별 상위 개만 유지하면 된다.
서브태스크 4에서는 서버가 하나이고 번 쿼리가 없으며 모든 쌍이 한 번만 제출된다. 완료 이벤트를 큐로 처리하며 사용자 랭킹 집합만 유지하면 된다.
서브태스크 5에서는 쌍이 중복되지 않으므로 완료된 쌍을 검사하는 해시 집합이 필요 없다. 최소 힙, 문제별 상위 개, 사용자 랭킹 집합을 함께 유지한다.
전체 제약에서는 여기에 완료된 쌍의 해시 집합을 추가한다.
복잡도
각 제출은 완료 이벤트 최소 힙에 한 번 삽입되고 한 번 삭제된다. 사용자 랭킹의 삭제와 삽입은 각각 이고, 문제별 상위 개 갱신은 이다.
한 테스트 케이스의 시간 복잡도는 로 볼 수 있으며, 공간 복잡도는 이다. 전체 입력에서는 이므로 충분하다.
Solution written by GPT5.6
