8217 유성 (Meteors)

유성 (8217 Meteors)

https://www.acmicpc.net/problem/8217 (BOJ Meteors)

http://www.spoj.com/problems/METEORS (SPOJ Meteors)

http://codeforces.com/blog/entry/45578 (Codeforces parellel binary search tutorial)

블로그 만든 기념으로 최근에(거의 한달 전인 것 같지만) 풀었던 문제중 꽤 난이도가 있었던 문제를 올려본다. ㅎ

이 문제 번역도 내가했다 ㅋㅋ

번역글 도저히 못보겠다 생각되면 원문을 보시길 바랍니다. (ㅈㅅㅈㅅ)

parallel binary search(pbs) 알고리즘으로 푸는 가장 대표적인 문제인 것 같다.

코드포스 가서 pbs검색해보면 제일 처음에 포스팅 된 글에서 meteors 문제를 통해 설명하는 것을 볼 수 있다.

근데, 코딩한지 너무 오래돼서 어디서 버벅였는지 기억이 안난다. ㅋㅋ

일단 펜윅을 썼는데, 처음에 Petr가 소개하는 Fenwick Range Update를 그대로 가져와서 쓰다가, 쿠사과님의 조언으로 그런짓을 할 필요가 없다는 걸 알게 됐다. 여기서 펜윅 구간 업뎃을 그대로 쓰면 unsigned long long 범위마저 초과해서 답이 없다. 그렇다고 Segment Tree를 쓰자니 메모리를 많이 먹는다. 내 기억엔 BOJ 메모리 부분이 세그먼트 트리를 쓰면 메모리초과가 났던 걸로 기억하는데, 정확하지는 않다.

아무튼 그래서 펜윅을 응용해서 자료구조 만들고, 나머지 pbs는 그냥 전형적인 pbs 코딩을 하면 된다.

#include <cstdio>
#include <vector>
using namespace std;
typedef unsigned long long ull;
vector<int> sect[300001];
vector<vector<int> > cp;
ull goal[300001];
struct Day{
    int l,r; ull cnt;
    Day(){} Day(int l, int r, ull cnt):l(l),r(r),cnt(cnt){}
};
struct Fenwick{
    int s,e;
    vector<ull> tree, tadd;
    Fenwick(){} Fenwick(int n):s(1),e(n),tree(n+1,0ULL){}
    void clear() { tree.clear(); tree.resize(e+1,0ULL); }
    void rupdate(int left, int right, ull by) {
        inupdate(left, by);
        inupdate(right+1, -by);
    }
    void inupdate(int at, ull by) {
        for(int i=at; i<=e && i; i+=i&-i) tree[i]+=by;
    }
    ull query(int at) {
        ull ans=0ULL;
        for(int i=at; i>=1; i&=(i-1)) ans+=tree[i];
        return ans;
    }
};
 
vector<Day> day(1);
int l[300001], r[300001];
int main() {
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1; i<=m; i++) {
        int x; scanf("%d",&x);
        sect[x].push_back(i);
    }
    Fenwick fen(m);
    for(int i=1; i<=n; i++) {
        scanf("%llu",&goal[i]);
    }
    int q; scanf("%d",&q);
    for(int i=1; i<=q; i++) {
        int l,r; ull cnt;
        scanf("%d%d%llu",&l,&r,&cnt);
        day.push_back(Day(l,r,cnt));
    }
    cp.resize(q+1, vector<int>());
    for(int i=1; i<=n; i++) l[i]=0, r[i]=q+1;
    while(true) {
        bool good=false;
        for(int i=1; i<=n; i++) {
            if(l[i]+1<r[i]) {
                cp[(l[i]+r[i])>>1].push_back(i);
                good=true;
            }
        }
        if(!good) break;
 
        int pi=1;
        for(int i=1; i<=q; i++) {
            //bring meteor shower!!
            if(!cp[i].size()) continue;
            for(int j=pi; j<=i; pi=++j) {
                if(day[j].l<=day[j].r) {
                    fen.rupdate(day[j].l,day[j].r,day[j].cnt);
                } else {
                    fen.rupdate(1,day[j].r,day[j].cnt);
                    fen.rupdate(day[j].l,m,day[j].cnt);
                }
            }
 
            for(int nara: cp[i]) {
                ull sum=0ULL;
                for(int k: sect[nara]) sum+=fen.query(k);
                int mid=(l[nara]+r[nara])>>1;
                if(sum>=goal[nara]) r[nara]=mid;
                else l[nara]=mid;
            }
            cp[i].clear();
        }
        fen.clear();
    }
 
    for(int i=1; i<=n; i++) {
        if(r[i]!=q+1) printf("%d\n", r[i]);
        else puts("NIE");
    }
    return 0;
}