BOJ)8217 유성

문제: icpc.me/8217

회원국이 커버하고있는 행성구역이 주어지고 날짜에 따른 유성 예보수가 주어질 때 각 회원국이 목표치로 정한 운석 샘플을 구하는데 걸리는 최소 날짜를 출력하는 문제이다.

각 날짜에 대해 나이브하게 계산을 해준다면 모든 날에 대해 단순히 K일을 커버하는 작업만 O(N*K)가 걸리게 된다.

이런 방법으로는 도저히 시간안에 문제를 해결할 수 없다.

따라서 새로운 방법이 필요한데 답으로 출력해야되는 모든 행성구역의 답의 범위를 lo~hi로 전부 잡아놓은 뒤 전체에 대하여 binary search를 돌리는 parallel binary search를 이용하자.

우선 답이 정해야하는 모든 구간에 대해 lo와 hi를 잡아준 뒤 

모든 구간에 대한 답이 결정될 때 까지 while문으로 반복한다.

이때 mid값은 답이 되어야 하므로 날짜를 의미하게 된다. 즉 모든 구간에 대해 mid날에 대한 질의를 저장해준 뒤

아래에서 질의들을 일괄적으로 처리해줄 수 있다. 날짜에 따른 유성 예보의 수는 구간쿼리를 log시간에 처리해주는 자료구조를 이용해주면 된다.

하지만 필자의 경우 lazy_propagation을 곁들인 segment tree를 이용하였는데 TLE를 보게되어 찾아보니 다른 사람들은 BIT를 많이 이용한걸 보고 BIT로 수정하니 AC를 받게되었다.

둘다 같은 시간복잡도를 가지고 있어서 무리없이 해결될 줄 알았는데 약간 충격을 먹은 상태였는데 

이러한 이유때문에 BIT 코드만 통과한거 같다.

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
typedef long long ll;
ll n, m, k, x[300030], y[300030], z[300030], lo[300030], hi[300030], tree[300030], g[300030];
vector<vector<ll>> unv, qry;
void update(ll pos, ll val) {
    while (pos <= m) {
        tree[pos] += val;
        pos += (pos&-pos);
    }
}
ll query(int pos) {
    ll ret = 0;
    while (pos > 0) {
        ret += tree[pos];
        pos -= (pos&-pos);
    }
    return ret;
}
void go(int h) {
    if (y[h] >= x[h])
        update(x[h], z[h]), update(y[h] + 1, -z[h]);
    else
        update(1, z[h]), update(y[h] + 1, -z[h]), update(x[h], z[h]);
}
int main() {
    scanf("%lld%lld", &n, &m);
    unv.resize(n + 1);
    for (int i = 1, t; i <= m; i++) {
        scanf("%lld", &t);
        unv[t].push_back(i);
    }
    for (int i = 1; i <= n; i++)
        scanf("%lld", &g[i]);
    scanf("%lld", &k);
    qry.resize(k + 1);
    for (int i = 1; i <= k; i++) 
        scanf("%lld%lld%lld", &x[i], &y[i], &z[i]);
    for (int i = 1; i <= n; i++) 
        lo[i] = 1, hi[i] = k + 1;
    bool f = 1;
    while (f) {
        f = 0;
        memset(tree, 0, sizeof(tree));
        for (int i = 1; i <= n; i++) {
            if (lo[i] < hi[i]) {
                qry[(lo[i] + hi[i]) >> 1].push_back(i);
                f = 1;
            }
        }
        for (int i = 1; i <= k; i++) {
            go(i);
            while (qry[i].size()) {
                int idx = qry[i].back();
                qry[i].pop_back();
                ll sum = 0;
                for (auto next : unv[idx]) {
                    sum += query(next);
                    if (sum >= g[idx])break;
                }
                if (sum >= g[idx])
                    hi[idx] = i;
                else
                    lo[idx] = i + 1;
            }
        }
    }
    for (int i = 1; i <= n; i++)
        if (lo[i] == k + 1)
            puts("NIE");
        else
            printf("%d\n", lo[i]);
    return 0;
}