유성 (백준 8217)

안녕하세요. 오늘은 유성을 관측할 거에요.

문제

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

아이디어

그냥 PBS+segtree입니다 (사실 Fenwick tree 이기는 합니다).
하지만 오버플로우를 굉장히 주의해야합니다.
그래서 Fenwick tree에 저장할 때에는 상관이 없지만 sum에 더해서 합을 구할 때에는 제때제때 break를 해주어야합니다.

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
#define ll long long
using namespace std;

ll tree[303030] = { 0 }, N, M; //펜윅트리
void update(ll idx, ll val)
{
    while (idx < M + 1)
    {
        tree[idx] += val;
        idx += idx & -idx;
    }
}
ll NUM(ll idx)
{
    ll sum = 0;
    while (idx > 0)
    {
        sum += tree[idx];
        idx -= idx & -idx;
    }
    return sum;
}

ll owner[303030] = { 0 }, goal[303030] = { 0 };
vector <ll> land[303030];
ll Left[303030] = { 0 }, Right[303030] = { 0 }, Ans[303030] = { 0 };
vector <ll> check[303030];

void init()
{
    for (ll i = 1; i <= 300000; i++) check[i].clear();
    for (ll i = 1; i <= 300000; i++) tree[i] = 0;
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll Q, a, b, c;
    vector <pair <pair <ll, ll>, ll> > qry;

    cin >> N >> M;
    for (ll i = 1; i <= M; i++)
    {
        cin >> owner[i];
        land[owner[i]].push_back(i);
    }
    for (ll i = 1; i <= N; i++)
        cin >> goal[i];

    cin >> Q;
    for (ll i = 0; i < Q; i++)
    {
        cin >> a >> b >> c;
        qry.push_back({ {a,b},c });
    }
    for (ll i = 1; i <= N; i++)
    {
        Left[i] = 1;
        Right[i] = Q + 1;
        Ans[i] = -1;
    }

    while (true)
    {
        init();
        ll IsDone = true;
        for (ll i = 1; i <= N; i++)
        {
            if (Left[i] < Right[i])
            {
                IsDone = false;
                check[(Left[i] + Right[i]) / 2].push_back(i);
            }
        }
        if (IsDone) break;

        for (ll i = 1; i <= Q; i++)
        {
            ll qryidx = i - 1;
            if (qry[qryidx].first.first <= qry[qryidx].first.second)
            {
                update(qry[qryidx].first.first, qry[qryidx].second);
                update(qry[qryidx].first.second + 1, -qry[qryidx].second);
            }
            else
            {
                update(1, qry[qryidx].second);
                update(qry[qryidx].first.second + 1, -qry[qryidx].second);
                update(qry[qryidx].first.first, qry[qryidx].second);
            }

            for (ll NowOwner : check[i])
            {
                ll sum = 0;
                for (ll NowLand : land[NowOwner]) //모든 땅을 보면서
                {
                    sum += NUM(NowLand); //지금까지 쌓인 유성우의 수를 센다
                    if (sum >= goal[NowOwner]) break;
                }

                if (sum >= goal[NowOwner]) //목표를 달성했으면
                {
                    Ans[NowOwner] = i; //저장
                    Right[NowOwner] = i;
                }
                else Left[NowOwner] = i + 1;
            }
        }
    }

    for (ll i = 1; i <= N; i++)
    {
        if (Ans[i] == -1) cout << "NIE\n";
        else cout << Ans[i] << "\n";
    }
}

감사합니다.