백준 25620 - 슬라임 키우기 (C++)

문제

• 문제 링크

  
   BOJ 25620 - 슬라임 키우기 
  

• 문제 요약

$N$마리 슬라임의 크기와 $Q$개의 업데이트 쿼리가 주어진다.
모든 쿼리의 적용이 끝난 후 최종 슬라임들의 상태를 출력해보자.

• 제한

TL : $2$ sec, ML : $1024$ MB




$1 ≤ N, Q ≤ 200 000$

$0 ≤ N_i, x_i, y_i ≤ 10^9$

알고리즘 분류

• 자료 구조(data structures)
• 우선순위 큐(priority_queue)
• 수학(math)
• 정수론(number_theory)

풀이

간단하면서도 재밌는 관찰이 필요한 문제였다.
우선 항상 최솟값 ~ $x$의 범위를 빠르게 추려내야 하므로 최솟값 우선순위 큐를 떠올려볼 수 있다.

이제 범위를 보면, $0 ≤ N_i, x_i, y_i ≤ 10^9$ 이고 각 쿼리마다 $a[i]$에 작용하는 연산은 곱셈이다.
즉, 다음의 사실을 알 수 있다.

• $a[i] == 0$ $||$ $y == 0$ 이라면 해당되는 모든 $a[i]$ 는 영원히 $0$이다.
• $y == 1$ 이라면 $a[i] <= x$ 인 모든 $a[i]$ 는 아무런 변화가 없다.
• 위 사실에 따라, $2 ≤ y$에서 $a[i] <= x$ 인 $a[i]$ 는 항상 $2$배 이상 증가한다.

$1$에 의해 $a[i] == 0$ 인 $i$는 들고 있을 필요가 없으므로 따로 담아두자.
그럼 결국 $y == 1$ 일 때를 제외하면 $3$의 관찰을 항상 성립하도록 할 수 있고 $x ≤ 10^9$ 이므로 제한 시간 내에 충분히 해결할 수 있다.

전체 코드

#include<bits/stdc++.h>
#define ll long long
using namespace std;
 
priority_queue <ll> Q, an;
ll n, q, i;
 
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    for (cin >> n >> q; n--;)
        cin >> i, Q.push(-i);
    for (int x, y; q--;)
    {
        while (Q.size() && !Q.top()) an.push(0), Q.pop();
        if (cin >> x >> y; y ^ 1)
        {
            queue <ll> t;
            while (Q.size() && -Q.top() <= x) t.push(Q.top()), Q.pop();
            while (t.size()) Q.push(t.front() * y), t.pop();
        }
    }
    while (Q.size()) an.push(Q.top()), Q.pop();
    while (an.size()) cout << -an.top() << ' ', an.pop();
}

comment

끝