代码

#include<bits/stdc++.h>
#define maxn 100010
#define all 100000LL
using namespace std;
typedef long long ll;
template<typename T> inline void read(T &x)
{
    x=0;char c=getchar();bool flag=false;
    while(!isdigit(c)){if(c=='-')flag=true;c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    if(flag)x=-x;
}
ll n,m,k,top,tot;
ll a[maxn],s[maxn],c[maxn],d[maxn],num[maxn],ans[maxn];
bool vis[maxn];
struct node
{
    ll v,id;
}st[maxn];
bool operator <(const node &a,const node &b)
{
    return a.v<b.v;
}
vector<int> ve[maxn];
priority_queue<node> q;
int main()
{
    read(n),read(m),read(k);
    for(int i=1;i<=n;++i)
    {
        read(a[i]),read(s[i]),read(c[i]),read(d[i]);
        if(!d[i]) ve[all].push_back(i);
        else ve[min(all,(c[i]+d[i]-1)/d[i])].push_back(i);
    }
    for(int i=all;i;--i)
    {
        ll now=m;
        for(int j=0;j<ve[i].size();++j)
            q.push((node){a[ve[i][j]]+s[ve[i][j]],ve[i][j]});
        while(!q.empty()&&now)
        {
            node x=q.top();
            q.pop();
            if(!vis[x.id])
            {
                vis[x.id]=true,ans[all]+=x.v,num[x.id]++,now--;
                if(c[x.id]!=1) q.push((node){a[x.id],x.id});
            }
            else
            {
                ll val=min(now,c[x.id]-num[x.id]-(i-1)*d[x.id]);
                ans[all]+=x.v*val,num[x.id]+=val,now-=val;
                if(c[x.id]!=num[x.id]) st[++top]=(node){a[x.id],x.id};
            }
        }
        while(top) q.push(st[top--]);
    }
    while(!q.empty()) q.pop();
    for(int i=1;i<=n;++i)
    {
        if(!num[i]) continue;
        tot+=num[i];
        if(num[i]==1) q.push((node){-a[i]-s[i],i});
        else q.push((node){-a[i],i});
    }
    for(int i=all-1;i;--i)
    {
        ans[i]=ans[i+1];
        while(!q.empty()&&tot>i*m)
        {
            node x=q.top();
            q.pop(),x.v*=-1;
            if(num[x.id]==1) ans[i]-=x.v,num[x.id]--,tot--;
            else
            {
                ll val=min(num[x.id]-1,tot-i*m);
                ans[i]-=x.v*val,num[x.id]-=val,tot-=val;
                if(num[x.id]==1) q.push((node){-a[x.id]-s[x.id],x.id});
                else q.push((node){-a[x.id],x.id});
            }
        }
    }
    for(int i=1,p;i<=k;++i) read(p),printf("%lld\n",ans[p]);
    return 0;
}

评测结果