Can anyone please suggest some resouces for learning Flow in Graphs (A-Z)? video resources if possible.
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3839 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3612 |
7 | Geothermal | 3569 |
7 | cnnfls_csy | 3569 |
9 | ecnerwala | 3494 |
10 | Um_nik | 3396 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | Um_nik | 164 |
2 | maomao90 | 160 |
3 | -is-this-fft- | 159 |
4 | atcoder_official | 158 |
4 | awoo | 158 |
4 | cry | 158 |
7 | adamant | 155 |
8 | nor | 154 |
9 | TheScrasse | 153 |
10 | maroonrk | 152 |
Can anyone please suggest some resouces for learning Flow in Graphs (A-Z)? video resources if possible.
Any approach for this question? Only approach i could think of was greedy around centroid. https://www.codechef.com/problems/ADMN?tab=statement
Given an array A of n elements representing the monsters and an array B of q elements representing the heros. The i−th type of monster is represented by A[i][0] , A[i][1] and A[i][2] which means a monster of the i−th type is present at each integer co-ordinate from A[i][0] to A[i][1] and having a strength of A[i][2]. The i−th type of hero is represented by B[i][0] and B[i][1] which means a hero of strength B[i][1] will appear at the integer point B[i][0] after i seconds. When the i−th hero appears it will destroy each and every monster present at B[i][0] and having a strength less than B[i][1] . For each i you have to determine the number of monsters left after the i−th hero has completed their task.
The first line of input contains two integers N (1≤N≤105) and Q (1≤Q≤105) — the number of monsters and the number of heroes respectively.The next n lines contains 3 integers A[i][0],A[i][1],A[i][2] (1≤A[i][0]≤A[i][1]≤105;1≤A[i][2]≤109) each describing the monsters. The next q lines contains 2 integers B[i][0],B[i][1] (1≤B[i][0]≤105;1≤B[i][1]≤109) each describing the heroes.
Print q space separated integers — the i−th number should be equal to the number of monsters left after the i−th hero has completed their task.
3 2 1 3 7 2 5 4 4 8 6 3 5 5 8
11 9
Here is My Code:
struct seg_tree{
vector<int> st,lazy;
int size;
seg_tree(int n){
this->size=n;
st.resize(4*n);
lazy.resize(4*n);
}
void update(int start,int end){
update(0,0,size-1,start,end);
}
void update(int node,int l,int r,int start,int end){
if(lazy[node]!=0){
st[node]+=(lazy[node]*(r-l+1));
if(l!=r){
lazy[2*node+1]+=lazy[node];
lazy[2*node+2]+=lazy[node];
}
lazy[node]=0;
}
if(l>end || r<start)
return;
if(l>=start && r<=end){
st[node]+=(r-l+1);
if(l!=r){
lazy[2*node+1]++;
lazy[2*node+2]++;
}
return;
}
int mid=l+(r-l)/2;
update(2*node+1,l,mid,start,end);
update(2*node+2,mid+1,r,start,end);
st[node]=st[2*node+1]+st[2*node+2];
}
int query(int start,int end){
return query(0,0,size-1,start,end);
}
int query(int node,int l,int r,int start,int end){
if(lazy[node]!=0){
st[node]+=(lazy[node]*(r-l+1));
if(l!=r){
lazy[2*node+1]+=lazy[node];
lazy[2*node+2]+=lazy[node];
}
lazy[node]=0;
}
if(end < l || start > r)
return 0;
if(l>=start && r<=end){
int val=st[node];
st[node]=0;
return val;
}
int mid=l+(r-l)/2;
return query(2*node+1,l,mid,start,end)+query(2*node+2,mid+1,r,start,end);
}
};
void solve(){
int n,m;
cin>>n>>m;
vector<vector<int>> monst(n,vector<int>(3)),hero(m,vector<int>(4));
int total=0,mx=0;
for(int i=0;i<n;i++){
cin>>monst[i][0]>>monst[i][1]>>monst[i][2];
mx=max({mx,monst[i][0],monst[i][1]});
total+=(monst[i][1]-monst[i][0]+1);
}
unordered_map<int,int> high_before;
for(int i=0;i<m;i++){
cin>>hero[i][0]>>hero[i][1];
hero[i][2]=i;
mx=max(mx,hero[i][0]);
if(high_before[hero[i][0]] >= hero[i][1]){
hero[i][3]=0;
}else{
hero[i][3]=1;
high_before[hero[i][0]]=hero[i][1];
}
}
sort(all(monst),[&](vector<int>& a,vector<int>& b){
return a[2]<b[2];
});
sort(all(hero),[&](vector<int>& a,vector<int>& b){
return a[1]<b[1];
});
vector<int> ans(m);
int i=0,j=0;
seg_tree *tree=new seg_tree(mx+1);
while(j<m){
while(i<n && (monst[i][2]<hero[j][1])){
int start=monst[i][0],end=monst[i][1];
tree->update(start,end);
i++;
}
if(hero[j][3]==0){
j++;
continue;
}
int curr_idx=hero[j][2];
// cout<<tree->query(hero[j][0]],hero[j][0]])<<endl;
int monst_at_pos=tree->query(hero[j][0],hero[j][0]);
ans[curr_idx]=monst_at_pos;
j++;
}
for(int i:ans){
total-=i;
cout<<total<<" ";
}
cout<<endl;
}
Название |
---|