Can you please indent your code and write some comments so people can understand what your logic is!
Once you find the least index of both the characters in t3 and t4 respectively, you are linearly calculating the combination(i.e. for each query your computation is going t4-t3). Try to optimize it by precomputing the values. I hope I have understood your logic. Please correct me if you I have misunderstood anything.
Thank you. You have understood the logic correctly. Now its time for me to think how to optimize the approach.
LABOUR! Totally waste of time…!! Not expected from an author like you
please check my sol it is giving correct answer for given test cases but on server it is giving WA…
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
string P;
ll q;
char a,b;
ll *c,*h,*e,*f,*ch,*ce,*cf,*hc,*he,*hf,*ec,*eh,*ef,*fc,*fh,*fe,l,r;
int main()
{
//freopen(“input.txt”,“r”,stdin);
cin>>P;
ll len=P.length();
c=(ll*)malloc(sizeof(ll)(len+1));
h=(ll)malloc(sizeof(ll)(len+1));
e=(ll)malloc(sizeof(ll)(len+1));
f=(ll)malloc(sizeof(ll)*(len+1));
c[0]=h[0]=e[0]=f[0]=0;
ch=(ll*)malloc(sizeof(ll)*(len));
ce=(ll*)malloc(sizeof(ll)*(len));
cf=(ll*)malloc(sizeof(ll)*(len));
hc=(ll*)malloc(sizeof(ll)*(len));
he=(ll*)malloc(sizeof(ll)*(len));
hf=(ll*)malloc(sizeof(ll)*(len));
ec=(ll*)malloc(sizeof(ll)*(len));
eh=(ll*)malloc(sizeof(ll)*(len));
ef=(ll*)malloc(sizeof(ll)*(len));
fc=(ll*)malloc(sizeof(ll)*(len));
fh=(ll*)malloc(sizeof(ll)*(len));
fe=(ll*)malloc(sizeof(ll)*(len));
for(int loop=0;loop<len;loop++)
{
if(P[loop]=='c')
{
c[loop+1]=c[loop]+1;
h[loop+1]=h[loop];
e[loop+1]=e[loop];
f[loop+1]=f[loop];
}
else if(P[loop]=='h')
{
c[loop+1]=c[loop];
h[loop+1]=h[loop]+1;
e[loop+1]=e[loop];
f[loop+1]=f[loop];
}
else if(P[loop]=='e')
{
c[loop+1]=c[loop];
h[loop+1]=h[loop];
e[loop+1]=e[loop]+1;
f[loop+1]=f[loop];
}
else if(P[loop]=='f')
{
c[loop+1]=c[loop];
h[loop+1]=h[loop];
e[loop+1]=e[loop];
f[loop+1]=f[loop]+1;
}
}
/*for(int check=0;check<=len;check++)
{
cout<<"C:"<<c[check];
}
cout<<"\n";
for(int check=0;check<=len;check++)
{
cout<<"H:"<<h[check];
}
cout<<"\n";
for(int check=0;check<=len;check++)
{
cout<<"E:"<<e[check];
}
cout<<"\n";
for(int check=0;check<=len;check++)
{
cout<<"F:"<<f[check];
}
cout<<"\n";*/
ch[0]=ce[0]=cf[0]=hc[0]=he[0]=hf[0]=ec[0]=eh[0]=ef[0]=fh[0]=fe[0]=fc[0]=0;
for(int loop=1;loop<len;loop++)
{
ch[loop]=(h[loop+1]-h[loop])*c[loop]+ch[loop-1];
ce[loop]=(e[loop+1]-e[loop])*c[loop]+ce[loop-1];
cf[loop]=(f[loop+1]-f[loop])*c[loop]+cf[loop-1];
hc[loop]=(c[loop+1]-c[loop])*h[loop]+hc[loop-1];
he[loop]=(e[loop+1]-e[loop])*h[loop]+he[loop-1];
hf[loop]=(f[loop+1]-f[loop])*h[loop]+hf[loop-1];
ec[loop]=(c[loop+1]-c[loop])*e[loop]+ec[loop-1];
eh[loop]=(h[loop+1]-h[loop])*e[loop]+eh[loop-1];
ef[loop]=(f[loop+1]-f[loop])*e[loop]+ef[loop-1];
fc[loop]=(c[loop+1]-c[loop])*f[loop]+fc[loop-1];
fh[loop]=(h[loop+1]-h[loop])*f[loop]+fh[loop-1];
fe[loop]=(e[loop+1]-e[loop])*f[loop]+fe[loop-1];
}
/* for(int check=0;check<len;check++)
{
cout<<“CH: “<<ch[check];
}
cout<<”\n”;
for(int check=0;check<len;check++)
{
cout<<“CE: “<<ce[check];
}
cout<<”\n”;
for(int check=0;check<len;check++)
{
cout<<“CF: “<<cf[check];
}
cout<<”\n”;*/
//cout<<"val "<<ec[5]<<endl;
cin>>q;
while(q–)
{
cin>>a>>b;
cin>>l>>r;
if(P[l]==P[r] || l==r)
cout<<“0”<<endl;
else
{
if(a==‘c’&&b==‘f’)
cout<<cf[r-1]-(f[r]*c[l-1])<<endl;
else if(a=='c'&&b=='e')
cout<<ce[r-1]-(e[r]*c[l-1])<<endl;
else if(a=='c'&&b=='h')
cout<<ch[r-1]-(h[r]*c[l-1])<<endl;
else if(a=='h'&&b=='c')
cout<<hc[r-1]-(c[r]*h[l-1])<<endl;
else if(a=='h'&&b=='e')
cout<<he[r-1]-(e[r]*h[l-1])<<endl;
else if(a=='h'&&b=='f')
cout<<hf[r-1]-(f[r]*h[l-1])<<endl;
else if(a=='e'&&b=='c')
cout<<ec[r-1]-(c[r]*e[l-1])<<endl;
else if(a=='e'&&b=='h')
cout<<eh[r-1]-(h[r]*e[l-1])<<endl;
else if(a=='e'&&b=='f')
cout<<ef[r-1]-(f[r]*e[l-1])<<endl;
else if(a=='f'&&b=='c')
cout<<fc[r-1]-(c[r]*f[l-1])<<endl;
else if(a=='f'&&b=='h')
cout<<fh[r-1]-(h[r]*f[l-1])<<endl;
else if(a=='f'&&b=='e')
cout<<fe[r-1]-(e[r]*f[l-1])<<endl;
}
}
free(c);free(h);free(e);free(f);free(ch);free(ce);free(cf);
free(hc);free(he);free(hf);free(ec);free(eh);free(ef);free(fc);free(fh);free(fe);
return 0;
}
This seems like a great long-challenge problem, and you gave fair warning with the “precalculation” tag.
The difficulty of getting the time down for full solution, gradually extending the precalc overhead, was just frustrating enough to make it interesting, with the benefit of seeing the restricted problem results move in the right direction. I ended up with a set of cumulative-pairs arrays calculated nicely in Python with:
# 1 where each character occurs
mask = tuple(
tuple( int(f == v) for f in full)
for v in cx )
# cumulative count of each character
cacc = tuple(
tuple(accumulate(mask[v]))
for v in cx )
# cumulative number of ordered pairs per ch. pair
pairsacc = tuple(
tuple(
tuple(accumulate( map(mul, cacc[v], mask[w]) ))
for w in cx )
for v in cx )
and calculation per query as described in the editorial. (accumulate is imported from itertools and mul from operator).