I recently gave Atcoder Round 163 and could not solve this problem Can anyone explain the math behind this problem ?
# | User | Rating |
---|---|---|
1 | tourist | 3947 |
2 | jiangly | 3734 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3612 |
7 | ecnerwala | 3581 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | ksun48 | 3479 |
# | User | Contrib. |
---|---|---|
1 | awoo | 162 |
2 | maomao90 | 160 |
3 | nor | 156 |
4 | cry | 155 |
4 | adamant | 155 |
4 | atcoder_official | 155 |
4 | -is-this-fft- | 155 |
8 | maroonrk | 153 |
9 | SecondThread | 147 |
10 | Petr | 146 |
I recently gave Atcoder Round 163 and could not solve this problem Can anyone explain the math behind this problem ?
Hey Guys ! I am solving this problem
on Hackerearth which ultimately boils down to finding distinct integers in a range from L to R. I am having a hard time understanding how the bitset class is used with segment trees to find the solution. I am posting one of the accepted solutions. Can anyone please explain the logic.
#include<bits/stdc++.h>
using namespace std;
bitset<5001> seg_a[400001],seg_b[400001],rst;
int a[100005],b[100005];
void built_a(int node,int start,int end){
if(start==end){
seg_a[node].set(a[start]);
return;
}
int mid=(start+end)/2;
built_a(2*node,start,mid);
built_a(2*node+1,mid+1,end);
seg_a[node]=(seg_a[2*node]|seg_a[2*node+1]);
}
void built_b(int node,int start,int end){
if(start==end){
seg_b[node].set(b[start]);
return;
}
int mid=(start+end)/2;
built_b(2*node,start,mid);
built_b(2*node+1,mid+1,end);
seg_b[node]=(seg_b[2*node]|seg_b[2*node+1]);
}
bitset<5001> query_a(int node,int start,int end,int L,int R){
if(R<start||end<L)return rst;
if(start>=L && end<=R)return seg_a[node];
int mid=(start+end)/2;
return query_a(2*node,start,mid,L,R)|query_a(2*node+1,mid+1,end,L,R);
}
bitset<5001> query_b(int node,int start,int end,int L,int R){
if(R<start||end<L)return rst;
if(start>=L && end<=R)return seg_b[node];
int mid=(start+end)/2;
return (query_b(2*node,start,mid,L,R)|query_b(2*node+1,mid+1,end,L,R));
}
int main(){
int n;cin>>n;
for(int i=0;i<n;i++)cin>>a[i];
for(int i=0;i<n;i++)cin>>b[i];
built_a(1,0,n-1);
built_b(1,0,n-1);
cout<<seg_a[1].
int q;cin>>q;
int L1,R1,L2,R2;
while(q--){
cin>>L1>>R1>>L2>>R2;
int ans=(query_a(1,0,n-1,L1-1,R1-1)|query_b(1,0,n-1,L2-1,R2-1)).count();
cout<<ans<<"\n";
}
return 0;
}
Hello Friends, I recently faced a problem in my coding interview that i was unable to solve. The problem statement is -
A binary matrix of nxm was given, you have to toggle any column k number of times so that you can get the maximum number of rows having all 1’s.
for eg, n=3, m=3,
1 0 0 1 0 1 1 0 0
if k=2, then we will toggle column 2 and 3 once and we will get rows 1 and 3 with 1 1 1 and 1 1 1 i.e. all 1’s so answer is 2 as there are 2 rows with all 1’s.
if k=3, then we will toggle column 2 thrice and we will get row 2 with 1 1 1 i.e. all 1’s so answer is 1 as there is 1 row with all 1’s.
Please help me solve this question !
I am trying to solve this problem by running dfs from every node. I am getting TLE verdict. Please help me speed up my solution
Hello everyone ! please help in this question 682C - Алёна и дерево Alyona and the tree. I know how to find distance between two vertices but i have no clue what to do afer that.
Hey, guys, I have been working on this dfs problem for 2 days but I am not able to crack the logic. please suggest some hints or solution to this problem. Your text to link here...
Name |
---|