### codeworrior's blog

By codeworrior, 8 years ago, ,
i  m doing this (spoj SUBSEQ) problem on spoj...my algo is n*logn bt its giving me TLE ...hw this problem is to b solved ..i m using map...
here is the code...

int main()
{
map<int,int>list;
int t;
scanf("%d",&t);
while(t--)
{
list.clear();
int n;
scanf("%d",&n);
int tmp;
VI a,sum(n+1);
a.pb(0);
FOR(i,1,n)
{
scanf("%d",&tmp);
a.pb(tmp);
sum[i]=tmp+sum[i-1];
list[sum[i]]++;
}
list[0]++;
int64 ans=0;
int val;
for(int i=n;i>=0;i--)
{
list[sum[i]]--;
val=list[sum[i]-47];
if(val>0)
ans+=val;
}
printf("%lld\n",ans);
}
}

 8 years ago, # |   0 here is my code tht i chnged a bit still getting TLEint main(){  maplist; int t; scanf("%d",&t); while(t--) { list.clear(); int n; scanf("%d",&n); int tmp; VI sum(n+1); a.pb(0); list[0]++; int64 ans=0,val; FOR(i,1,n) { scanf("%d",&tmp); sum[i]=tmp+sum[i-1];            val=list[sum[i]-47]; ans+=val; list[sum[i]]++; } printf("%lld\n",ans); }}
 8 years ago, # |   0 here is the code ..previous one was incorrect..int main(){  maplist; int t; scanf("%d",&t); while(t--) { list.clear(); int n; scanf("%d",&n); int tmp; VI sum(n+1); list[0]++; int64 ans=0,val; FOR(i,1,n) { scanf("%d",&tmp); sum[i]=tmp+sum[i-1];            val=list[sum[i]-47]; ans+=val; list[sum[i]]++; } printf("%lld\n",ans); }}
•  8 years ago, # ^ |   0  val=list[sum[i]-47];If the map doesn't contain (sum[i]-47), then it is added in this line, so the size of the map increases and it affects the constant in the complexity of your solution.
•  8 years ago, # ^ |   0 thanx...
 8 years ago, # |   0 i got AC in 7.44 sec.. jst took the declaration of map inside the while loop and removed list.clear() statement..bt the bst solution in this prob is 0.66 sec..hw to achieve time of under 2 sec...thnx in advance...
•  8 years ago, # ^ |   0 map is very slow..you can write a hash table..
•  9 months ago, # ^ |   0 Can you please suggest a good implementation of a hash table?(I am not aware of it if it's in the STL; even if it is, I would like to have a custom hash)
•  9 months ago, # ^ |   +1 Good day to you,Sure, there is hash table in STL [C++], called "unordered_map" (which works fine without custom hash for types like int/long long/string/...).Their hash works pretty well, yet it is true that anti-hash tests can be so some precautions could be made.First: (Easier & yet not what you desired) is playing with max_load_factor().Second is making your own custom hash (as you sugested) which can be done by — for example — structure with "operator ()".Here you can refer to accepted code using what I suggested: 24> The structure25> The stl-map itself28> First methodHope it was at least a little-bit helpfulGood Luck & Have nice day!~/Morass
•  9 months ago, # ^ |   +5 Thank you. :)
 » 9 months ago, # |   0 Can you please explain me your logic ? I am getting WA bcoz my code works good only for positive integers :')