P1552 [APIO2012]派遣

  1 #include  2 #include
  3 #include  4 #include"vector"
  5 #define cint const int
  6 #define newnode() ++idx
  7 #include"iostream"
  8 using namespace std;
  9 int lch[3000010],rch[3000010];
 10 long long sum[3000010];
 11 int cnt[3000010];
 12 int idx;
 13 int root[100010];
 14 struct node{
 15     int a,b;
 16     inline bool operatorconst node &v)const{return av.a;}
 17 };
 18 node t[100010];
 19 
 20 int n,m;
 21 int b[100010],c[100010];
 22 long long l[100010];
 23 
 24 int rk[100010];
 25 long long ans;
 26 
 27 void merge(int &u,cint &v,int l,int r){
 28     
 29     
 30     if((!u)||(!v)){
 31         sum[u+v]=sum[u]+sum[v];
 32         cnt[u+v]=cnt[u]+cnt[v];
 33         u=v+u;
 34     }
 35     else if (l==r)
 36     {
 37         sum[u]+=sum[v];
 38         cnt[u]+=cnt[v];
 39         return ;
 40     }
 41     else {
 42         int mid =l+r>>1;
 43          merge(lch[u],lch[v],l,mid);
 44         merge(rch[u],rch[v],mid+1,r);
 45         sum[u]=sum[lch[u]]+sum[rch[u]];
 46         cnt[u]=cnt[lch[u]]+cnt[rch[u]];
 47     }
 48 }
 49 void ins(cint &u,cint &left,cint &right,cint &pos,cint &w){
 50     sum[u]+=w;
 51     ++cnt[u];
 52     if (right==left)return ;
 53     
 54             if(pos>1)){
 55             if(!lch[u])lch[u]=newnode();
 56             ins(lch[u],left,(left+right)>>1,pos,w);
 57         }else{
 58             if(!rch[u])rch[u]=newnode();
 59             ins(rch[u],(left+right)/2+1,right,pos,w);
 60         }
 61     
 62     
 63 }
 64 
 65 vectorint > v;
 66 
 67 int vv[600000];
 68 int bisearch(cint &u,cint &left,cint &right,cint &limit){
 69     if(!u)return 0;
 70     if(right>left)
 71     {
 72         if(sum[lch[u]]limit)
 73             return cnt[lch[u]]+bisearch(rch[u],(left+right)/2+1,right,limit-sum[lch[u]]);
 74         else
 75             return bisearch(lch[u],left,(left+right)>>1,limit);
 76     }
 77     else
 78     {
 79         
 80         //if (right==n+1)return 0;
 81         return min(cnt[u],limit/(vv[right]));
 82         //if(sum[u] 83     //    return 0;
 84        
 85     }
 86     
 87     
 88 }
 89 
 90 
 91 
 92 int main(){
 93 /*     n=5; root[1]=++idx;
 94     ins(root[1],1,n,2,2) ;
 95    root[2]=++idx;
 96     ins(root[2],1,n,2,3);
 97     cout 98     merge(root[2],root[1],1,n);
 99     cout100     
101     */
102     int i,j,k;
103     scanf("%d%d",&n,&m);
104     for(i=1;ii){
105         scanf("%d%d%lld",b+i,c+i,l+i);
106         t[i]={c[i],i};
107        vv[i]=c[i];
108     }
109     stable_sort(t+1,t+n+1);
110     
111     t[0].a=-1;int now = 0;
112     
113     
114     
115   //  sort(v.begin(),v.end());
116    // v.erase(unique(v.begin(),v.end()),v.end());
117     sort(vv+1,vv+1+n); int tote;
118      tote=unique(vv+1,vv+1+n)-vv-1;;
119     
120     
121     for(i=1;ii)
122     {
123     
124         k=t[i].b;
125         rk[k]=lower_bound(vv+1,vv+1+tote,t[i].a)-vv;
126         //cout
127         root[k]=newnode();
128         ins(root[k],1,n,rk[k],c[k]);
129        // cout
130         
131     }
132   //  cout
133     for(i=n;i;--i)
134     {
135     //    cout136         //    cout
137         ans=max(ans,l[i]*bisearch(root[i],1,n,m));
138       //  cout
139         if(b[i])merge(root[b[i]],root[i],1,n);
140        //  cout
141         
142     }
143     printf("%lld\n",ans);
144 }