백준 8217 유성

https://www.acmicpc.net/problem/8217

 

PBS 연습으로 유명한 문제

gemini에 따르면 PBS가 이 문제에서 처음 소개되었다고 한다.

 

각 결정 문제를 확인할 때 나이브하게 해도 된다는 점을 캐치하면 풀이는 어렵지 않다.

다만 옛날 문제라 그런지 먼가먼가인 부분이 좀 있다. 레이지세그 쓰면 TLE를 피하기 어려워서 펜윅을 써야 하고, 최대 합이 9e19라 int128을 쓰든 계산 중간에 끊든 해야 한다. 지금은 unsigned long long 쓰면 풀리던데 데추가 필요해 보인다. 

 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using tii = array<int,3>;
 
vector<int> G[303030], pbs[303030], buf[303030];
tii qry[303030];
ll seg[303030], N, M, Q, p[303030], no[303030], yes[303030];
 
void update(int i, ll v) {
    for (; i <= M; i += i & -i)
        seg[i] += v;
}
 
void update(int l, int r, ll v){
    update(l, v);
    if (r < M) update(r+1, -v);
}
 
ll query(int i){
    ll ret = 0;
    for (; i; i -= i & -i)
        ret += seg[i];
    return ret;
}
 
int main() {
    cin.tie(nullptr)->sync_with_stdio(0);
    
    cin >> N >> M;
    for (int i = 1, x; i <= M; i++){
        cin >> x;
        G[x].push_back(i);
    }
    for (int i = 1; i <= N; i++) cin >> p[i];
 
    cin >> Q;
    for (int i = 1; i <= Q; i++) {
        for (int j = 0; j < 3; j++)
            cin >> qry[i][j];
    }
 
    for (int i = 1; i <= N; i++) {
        pbs[Q+1 >> 1].push_back(i);
        no[i] = 0, yes[i] = Q+1;
    }
 
    int chk = 1;
    while (chk) {
        chk = 0;
        memset(seg, 0, sizeof seg);
        for (int i = 1; i <= Q; i++){
            auto [l,r,a] = qry[i];
            if (l <= r) update(l, r, a);
            else {
                update(1, r, a);
                update(l, M, a);
            }
            for (int x : pbs[i]) {
                chk = 1;
                ll sum = 0;
                for (int t : G[x]) {
                    if (sum >= p[x]) break;
                    sum += query(t);
                }
                if (sum >= p[x]) yes[x] = i;
                else no[x] = i;
                if (no[x]+1 < yes[x])
                    buf[no[x] + yes[x] >> 1].push_back(x);
            }
        }
        for (int i = 1; i <= Q; i++) {
            pbs[i] = buf[i];
            buf[i].clear();
        }
    }
    for (int i = 1; i <= N; i++) {
        if (yes[i] <= Q) cout << yes[i] << '\n';
        else cout << "NIE\n";
    }
}