代码

#include<bits/stdc++.h>
#define LL long long
#define RG register
#define R RG int
#define G if(++ip==ie)fread(ip=buf,1,N,stdin)
using namespace std;
const int N=2e5+9,M=1e6+9;
char buf[N],*ie=buf+N,*ip=ie-1;
int p[N],f[M];LL ans[M];
inline int in(){
    G;while(*ip<'-')G;
    R x=*ip&15;G;
    while(*ip>'-'){x*=10;x+=*ip&15;G;}
    return x;
}
struct Veg{
    int a,c,x;
    inline bool operator<(RG Veg&b){
        return a>b.a;
    }
}v[N];
int getf(R x){
    return x==f[x]?x:f[x]=getf(f[x]);
}
int main(){
    R n=in(),m=in(),k=in(),i,l=0;
    for(i=1;i<=n;++i){
        v[i].a=in();v[i+n].a=v[i].a+in();
        v[i].c=in()-1;v[i+n].c=1;
        if((v[i].x=in()))v[i+n].x=-(v[i].c/v[i].x+1);
    }
    for(i=1;i<=k;++i)l=max(l,p[i]=in());
    R tot=l*m,j=1,t=0,x;
    for(i=1;i<=tot;++i)f[i]=i;
    sort(v+1,v+(n*=2)+1);
    for(i=1;i<=n;++i){
        //printf("a%d c%d x%d\n",v[i].a,v[i].c,v[i].x);
        while(v[i].c){
            --v[i].c;
            x=v[i].x==0?tot:min((v[i].x>0?(v[i].c/v[i].x+1):-v[i].x)*m,tot);
            //printf("x%d ",x);
            x=getf(x);
            //printf("f%d\n",x);
            if(!x)break;
            //puts("get");
            --f[f[x]];ans[j]+=v[i].a;
            if(++t==m){
                if(++j>tot)goto F;
                t=0;ans[j]=ans[j-1];
            }
        }
    }
  F:for(++j;j<=tot;++j)ans[j]=ans[j-1];
    for(i=1;i<=k;++i)printf("%lld\n",ans[p[i]]);
    return 0;
}

评测结果