# O(NlogN) algorithm with segment tree

• ### oh ,I realised that using a heap is a better solution than this. so just ignore my solution :)

first you can define an array pair<int,int> q[],to save the p[i] (Profits)and c[i] (Capital).then sort the array q with the q.second(Capital) in the ascending order.
the by p[i]=q[i].first and c[i]=q[i].second ,we get the new p[] and c[].which c[] is in the ascending order.
my algorithm is :
1.each time,select the project with the max profit from all the projects that you can choose,which means the capital of the project <=W
2.then update W,W+=the profit you get
3.go to 1
do these steps k times and then return W.
now using a segment tree.val[i] means the max value of a interval,and pos[i] means the corresponding index in the array c.
in the step 1,
you can get the valid project interval by uper_bound() O(lgn)
then query in the segment tree O(lgn)
then update the value you chose(to remove it logically) O(lgn)
so when you do it k times ,the time complexity is O(klgn)
because there is a sort before this ,so at last ,the time complexity is O(nlgn)

``````#define lson id<<1
#define rson id<<1|1
#define maxn 50010
int val[4*maxn+5],pos[4*maxn+5];
pair<int,int> q[maxn];
int max(int a,int b)
{
return a>b?a:b;
}
int min(int a,int b)
{
return a<b?a:b;
}
void pushup(int id)
{
val[id]=max(val[lson],val[rson]);
if(val[id]==val[lson]) pos[id]=pos[lson];
else pos[id]=pos[rson];
return;
}
void build()
{

}
void update(int id,int l,int r,int index,int v)
{
if(l==r)
{
val[id]+=v;
pos[id]=l;
return;
}

int m=(l+r)/2;
if(index<=m) update(lson,l,m,index,v);
else update(rson,m+1,r,index,v);
pushup(id);
return;
}
pair<int,int> query(int id,int l,int r,int L,int R)
{
if((L<=l) && (r<=R))
{
return {pos[id],val[id]};
}
int ret;
int m=(l+r)/2;
pair<int,int> lv,rv;
if(L<=m) lv=query(lson,l,m,L,R);
if(R>m) rv=query(rson,m+1,r,L,R);
ret=max(lv.second,rv.second);
if(lv.second==ret) return lv;
return rv;
}
bool cmp(pair<int,int> a,pair<int,int> b)
{
return a.second<b.second;
}
class Solution {

public:
int findMaximizedCapital(int k, int W, vector<int>& p, vector<int>& c) {
int i,j;
int n=p.size();
if(!k) return W;
for(i=0;i<n;i++) {q[i].first=p[i],q[i].second=c[i];}
sort(q,q+n,cmp);
for(i=0;i<n;i++) p[i]=q[i].first;
for(i=0;i<n;i++) c[i]=q[i].second;
memset(val,-1,sizeof(int)*(n*4+5));
for(i=0;i<n;i++) update(1,0,n-1,i,p[i]+1);
for(i=1;i<=k;i++)
{
int r=upper_bound(c.begin(),c.end(),W)-c.begin();
r-=1;

if(r<0) break;
pair<int,int> tmp=query(1,0,n-1,0,r);
if(tmp.second==-1) break;
W+=tmp.second;
update(1,0,n-1,tmp.first,-(tmp.second+1));
}
return W;

}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.