건초 더미 (JUNGOL 8569)

https://jungol.co.kr/problem/8569?cursor=MjcsMSwxOQ==

---

아이디어

앞에서부터 하나씩 채워넣으면서 세그먼트 트리에 기록을 합니다. 그리고 i번째 인덱스까지 오면 i번째 이전에서 멈춰야하는 화살에 대해서 방어력이 가장 큰 k개의 건초더미로 막을 수 있는가? 를 기준으로 매개변수탐색을 해주면 됩니다.

---

소스코드

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

vector <ll> Nums; //1-인덱스

ll SumTree[1212121]={0},CntTree[1212121]={0};
void update(ll s,ll e,ll node,ll idx)
{
    if (idx<s || e<idx) return;
    SumTree[node]+=Nums[idx];
    CntTree[node]++;
    if (s==e) return;
    ll mid=(s+e)/2;
    update(s,mid,node*2,idx);
    update(mid+1,e,node*2+1,idx);
}
ll GetSum(ll s,ll e,ll node,ll num)
{
    if (num==0) return 0;
    if (num==CntTree[node]) return SumTree[node];
    if (s==e) return Nums[s]*num;
    ll mid=(s+e)/2;

    //가장 큰 num개 고르기
    return GetSum(s,mid,node*2,max((ll)(0),num-CntTree[node*2+1]))+GetSum(mid+1,e,node*2+1,min(num,CntTree[node*2+1]));
}

ll QueryAns[303030]={0}, Defend[303030]={0};
vector <pair <ll,ll> > Query[303030];

int main() 
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll N,Q,i,X,P;

    cin>>N>>Q;
    Nums.push_back(0);
    for (i=1;i<=N;i++)
    {
        cin>>Defend[i];
        Nums.push_back(Defend[i]);
    }
    sort (Nums.begin(),Nums.end());

    for (i=0;i<Q;i++)
    {
        cin>>X>>P;
        Query[X].push_back({P,i});
    }

    for (i=1;i<=N;i++)
    {
        update(1,N,1,lower_bound(Nums.begin(),Nums.end(),Defend[i])-Nums.begin());
        for (auto temp:Query[i])
        {
            ll Left=1,Right=i,Mid,Ans=2e9;
            while (Left<=Right)
            {
                Mid=(Left+Right)/2;
                if (GetSum(1,N,1,Mid)>=temp.first) //방어 가능
                {
                    Ans=Mid;
                    Right=Mid-1;
                }
                else Left=Mid+1;
            }
            if (Ans==2e9) QueryAns[temp.second]=-1;
            else QueryAns[temp.second]=Ans;
        }
    }

    for (i=0;i<Q;i++)
        cout<<QueryAns[i]<<"\n";
}