25961 - 스코어보드 보기 귀찮아

step 1

지수의 등수를 계산하는 것부터 해봅시다. 만약 지수보다 더 위에 있는 사람이 문제를 풀었다면 그 경우 지수의 등수에 아무런 영향이 없습니다. 지수보다 등수가 낮은 사람이 문제를 풀었어도 등수에 영향이 없습니다. 정확히 지수와 같은 문제를 풀었으면서 마지막 문제를 지수보다 늦게 푼 사람이 한 문제를 더 푸는 경우 지수의 등수가 하나 내려갑니다.

지수가 문제를 푼 경우 지수의 등수는 {푼 문제 수가 지수와 같거나 더 많은 사람의 수} + 1입니다. 만약 지수가 5문제를 풀었다면 5문제 이상 푼 사람 수 +1이 되는 것입니다. 이것은 푼 문제 수를 기준으로 부분합처럼 값을 저장해 두면 쉽게 구할 수 있습니다.

step 2

이제 수상권에 들기 위해 풀어야 하는 문제 수를 구해봅시다. 지수의 등수가 S보다 낮으면 문제를 더 풀 필요가 없습니다.

지수가 풀어야 하는 문제 수를 기준으로 이분탐색을 합니다. 지수가 문제를 푼 경우 지수의 등수는 {푼 문제 수가 지수와 같거나 더 많은 사람의 수} + 1임을 기억합니다. 이것 역시 부분함을 이용하면 쉽게 해결할 수 있습니다.

코드

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<set>
using namespace std;
int b[600000], s[600000],back[600000];
int main() {
	int n, m, i,q,l,sol;
	scanf("%d%d%d", &n, &m, &q);
	for (i = 1;i <= n;i++) back[i] = -1;
	s[0] = n;
	l = n; sol = 0;
	for (i = 1;i <= q;i++) {
		int x;
		scanf("%d", &x);
		if (b[x] == sol && back[x]==sol) {
			l++;
		}
		if (b[x] == sol-1) {
			back[x] = sol;
		}
		b[x]++;
		s[b[x]]++;
		if (x == 1) {
			l = s[b[x]];
			sol++;
		}
		int up = 0;
		if (l > m) {
			int ss = sol + 1, ee = 500100;
			while (ss < ee) {
				int mi = (ss + ee) / 2;
				if (s[mi] + 1 <= m) ee = mi; else ss = mi + 1;
			}
			up = ss - sol;
		}
		printf("%d %d\n", l,up);
	}
	return 0;
}