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);
}
}
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);
}
}
Using Hash...
AC code down:
#include<iostream>
#include<cstdio>
#include<map>
#define REP(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef long long LL;
typedef map<LL,int>::iterator It;
int t;
void solve()
{
scanf("[^/n]");
int n;scanf("%d",&n);
LL s=0,ans=0,t;
map<LL,int> M;
M[0]=1;
REP(i,n)
{
scanf("%lld",&t);s+=t;
It a=M.find(s-47);
if(a!=M.end()) ans+=(*a).second;
a=M.find(s);
if(a!=M.end()) (*a).second++;
else M[s]=1;
}
cout<<ans<<endl;
}
int main()
{
cin>>t;
while(t--)
{
solve();
}
}
scanf("[^/n]"); - what does it mean?
Also, you wrote your comment in russian site version.
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.
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)
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 structure
25> The stl-map itself
28> First method
Hope it was at least a little-bit helpful
Good Luck & Have nice day!
~/Morass
Thank you. :)