백준 25606 - 장마 (C++)

문제

• 문제 링크

  
   BOJ 25606 - 장마 
  

• 문제 요약

$N$일동안 비가 내린다.
장마 시작 $t$일 후 내리는 비는 상자에 $a_i$만큼 물을 채운다.

보관된 상자에선 매일 $M$만큼의 물이 증발할 때, 아래 두 쿼리를 수행하는 프로그램을 작성하자.



$1$ $t$ : 장마 시작 $t$일 후, 모든 상자에 들어있는 물의 양의 합은 무엇인가$?$

$2$ $t$ : 장마 시작 $t$일 후, 모든 상자에서 증발하는 물의 양의 합은 무엇인가$?$

• 제한

TL : $1$ sec, ML : $512$ MB




$1 ≤ N, Q ≤ 10^5$

$1 ≤ M, a_i ≤ 10^4$

알고리즘 분류

• 누적 합 (prefix_sum)

풀이

쿼리가 들어올 때마다 답을 계산하기엔 조금 귀찮아 보인다.

$N ≤ 10^5$이고 각 $N_i$에서 존재하는 답의 상태는 $2$가지 이므로, $1, 2, ... , N$번째 날에 대한 답을 전처리 해두자.
이 경우 $i$가 단조 증가하기 때문에, 답을 계산하기 좀 더 편할 것이다.

나는 집합에서 { 상자의 수명, 상자의 처음 인덱스 } 의 형태로 관리해주며 답을 계산했는데, 이 과정에선 다양한 방법이 있을 듯 하다.

여튼 그렇게 모든 $N_i$에 대한 답을 전처리 했다면, 쿼리마다 $O(1)$에 응답할 수 있다.

전체 코드

#include<bits/stdc++.h>
using namespace std;
 
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, m, q; cin >> n >> m >> q;
 
    vector <int> a(n);
    for (int& i : a) cin >> i;
 
    vector <int> sum(n + 1), sub(n + 1);
    set <pair<int, int>> S;
    for (int i(1), res{}, _res{}; i <= n; i++)
    {
        sum[i] = res += a[i - 1];
        sub[i] = _res;
        S.insert({ i - 1 + ceil((double)a[i - 1] / m), i - 1 });
 
        _res = S.size() * m;
        while (1)
        {
            if (!S.size()) break;
            auto [x, y](*S.begin());
            if (x ^ i) break;
 
            _res -= m * (x - y) - a[y];
            S.erase(S.begin());
        }
        res -= _res;
    }
    for (int op, t; q--;)
    {
        cin >> op >> t;
        cout << (op & 1 ? sum : sub)[t] << '\n';
    }
}

comment

끝