Submission #69875629

---

Source Code Expand

#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
const int maxn = 2e4+5;
int w[maxn],v[maxn];
class SegmentTree
{
public:
    gp_hash_table<int,long long> a[4 * maxn];
    inline void push_up(int rt) //向上更新
    {
        a[rt].clear();
        for (auto &i:a[rt*2])
        {
            for (auto &j:a[rt*2+1])
            {
                 if (i.first+j.first<=500)
                    a[rt][i.first+j.first]=max(a[rt][i.first+j.first],i.second+j.second);
            }
        }
    }
    void build(int l, int r, int rt) //从l到r建立线段树
    {
        if (l == r)
        {
            a[rt][w[l]]=v[l];
            a[rt][0]=0;
            return;
        }
        int mid = (l + r) / 2;
        build(l, mid, rt * 2);
        build(mid + 1, r, rt * 2 + 1);
        push_up(rt);
    }
    gp_hash_table<int,long long> query(int x, int y, int l, int r, int rt,int c) //线段树区间为从l到r，询问区间x到y的和
    {
        if (x <= l && y >= r)
            return a[rt];
        int mid = (l + r) / 2;
        gp_hash_table<int,long long> ans;
        if (x <= mid)
            ans = query(x, y, l, mid, rt * 2,c);
        if (y > mid)
        {
            auto rr=query(x, y, mid + 1, r, rt * 2 + 1,c);
            gp_hash_table<int,long long> ll;
            swap(ll,ans);
            ll[0]=0;
            for (auto &i:ll)
            {
                for (auto &j:rr)
                {
                    if (i.first+j.first<=c)
                        ans[i.first+j.first]=max(ans[i.first+j.first],i.second+j.second);
                }
            }
        }
        return ans;
    }
}st;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n;
    cin>>n;
    for (int i=1;i<=n;i++)
        cin>>w[i]>>v[i];
    st.build(1,n,1);
    int q;
    cin>>q;
    while (q--)
    {
        int l,r,c;
        cin>>l>>r>>c;
        auto tmp=st.query(l,r,1,n,1,c);
        long long ans=0;
        for (auto &i:tmp)
            if (i.first<=c)
                ans=max(ans,i.second);
        cout<<ans<<'\n';
    }
}

Submission Info

Judge Result