Boj 18045) Frogs

문제

백준 18045

설명

Frog 하나 당 범위를 하나씩 계산하면 터짐.

그러니까 무조건 시간복잡도를 선형이나 로그로 맞춰야함.

이때 아이디어는 Frog 의 시작과 끝 범위를 미리 기록해놓는 것.

그리고 Frogs 들을 보관해놓는 통에 해당 Frog 의 시작지점에 가면 넣고 끝지점에 가면 빼주면 됨.

이때 binary tree 를 이용하는 set 을 써서 상위 3마리만 계산하면 로그단위로 정렬이 가능함.

시간 복잡도

O(n*log(n))

코드

struct Frog { int r, s; };
Frog frogs[200001];
vector<int> startTB[200001], endTB[200001];
int n;

int main()
{
	int t, tmp1, tmp2;
	cin >> t;
	while (t--)
	{
		cin >> n;
		for (int i = 0; i < n; i++)
		{
			startTB[i].clear();
			endTB[i].clear();
		}

		for (int i = 0; i < n; i++) {
			cin >> frogs[i].r >> frogs[i].s;
			startTB[clamp(i - frogs[i].r, 0, n-1)].push_back(i);
			endTB[clamp(i + frogs[i].r, 0, n-1)].push_back(i);
		}
	
		int ans = -1, cnt;
		set<pair<int, int>, greater<pair<int, int>>> keeps;
		for (int i = 0; i < n; i++)
		{
			for (auto s : startTB[i])
				keeps.insert({ frogs[s].s, s });
			cnt = 0; tmp1 = 0;
			for (auto iter = keeps.begin(); iter != keeps.end() && cnt < 3; iter++, cnt++)
				tmp1 += iter->first;
			ans = max(ans, tmp1);
			for (auto s : endTB[i])
				keeps.erase({ frogs[s].s, s });
		}
	
		cout << ans << '\n';
	}
}