We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
#include<map>#include<set>#include<list>#include<cmath>#include<ctime>#include<deque>#include<queue>#include<stack>#include<string>#include<bitset>#include<cstdio>#include<limits>#include<vector>#include<climits>#include<cstring>#include<cstdlib>#include<fstream>#include<numeric>#include<sstream>#include<iostream>#include<iomanip>#include<algorithm>#include<unordered_map>usingnamespacestd;vector<int>maxh,minh;/*void swap(int &a, int &b){ int t=a; a=b; b=t;}*/intparent(inti){return(i-1)/2;}inttop(vector<int>maxh){returnmaxh[0];}voidheapifymx(){intin=maxh.size()-1;while(in>0){if(maxh[parent(in)]<maxh[in])swap(maxh[parent(in)],maxh[in]);in=parent(in);}}voidheapifymn(){intin=minh.size()-1;while(in>0){if(minh[parent(in)]>minh[in])swap(minh[parent(in)],minh[in]);in=parent(in);}}voidinsertmx(intvalue){cout<<max.size();maxh.push_back(value);heapifymx();}voidinsertmn(intvalue){minh.push_back(value);heapifymn();}voidheapmx(){intin=0;while(2*in+1<maxh.size()){intl=2*in+1;ints=l;if(2*in+2<maxh.size()){intr=2*in+2;if(maxh[r]>maxh[l])s=r;}if(maxh[in]>maxh[s]){break;}swap(maxh[in],maxh[s]);in=s;}}voidheapmn(){intin=0;while(2*in+1<maxh.size()){intl=2*in+1;ints=l;if(2*in+2<maxh.size()){intr=2*in+2;if(maxh[r]<maxh[l])s=r;}if(maxh[in]<maxh[s]){break;}swap(maxh[in],maxh[s]);in=s;}}intdeletemx(){intr=maxh[0];maxh[0]=maxh[maxh.size()-1];maxh.resize(maxh.size()-1);heapmx();returnr;}intdeletemn(){intr=minh[0];minh[0]=minh[minh.size()-1];minh.resize(minh.size()-1);heapmn();returnr;}floatmedian(){if(maxh.size()-minh.size()>1){insertmn(deletemx());}elseif(minh.size()-maxh.size()>1){insertmx(deletemn());}if(maxh.size()==minh.size())return(top(maxh)+top(minh))/2;elsereturn(maxh.size()>minh.size())?top(maxh):top(minh);}intmain(){intn;cin>>n;inta;maxh.clear();minh.clear();for(inti=0;i<n;i++){cin>>a;if(maxh.size()==0)insertmx(a);else{if(a>top(maxh))insertmn(a);elseinsertmx(a);}cout<<setprecision(1)<<fixed<<median()<<endl;}return0;}
Why does it give segmentation fault
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Heaps: Find the Running Median
You are viewing a single comment's thread. Return to all comments →
Why does it give segmentation fault