TLE with "HELP MARTHA"

link to the problem:

approach: firstly i am storing the number of occurences of every character “U”,“D”,“R”,“L” in a map named str. then i am storing the required number of occurences of each “U”,“D”,“R”,“L” in a map req. And if all the occurences in the map str are greater then the required occurences which are stored in map req, then i am returning "YES " with the count else return “NO”.
getting tle but the time complexity of code is around O(10^7)…
Please help me…

link to my solution:
https://www.codechef.com/viewsolution/37012072

#include<bits/stdc++.h>
#define lli long long int
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL);
using namespace std;
int main()
{
fastio;
lli t;
cin>>t;
while(t- -)
{
string s;
cin>>s;
map<char,lli>str;

    for (int i=0;i<s.size();i++)
    {
        
            str[s[i]]++;
            
    }
    
    lli x,y;
    cin>>x>>y;
    lli q;
    cin>>q;
    while(q- -)
    { 
        lli count=0;
        map<char,lli>req;
        req['R']=0;
        req['L']=0;
        req['U']=0;
        req['D']=0;
        lli x1,y1;
        cin>>x1>>y1;
        
        if (x1>x)
        {
            req['R']=x1-x;
            count+=x1-x;
        }
        if (x1<x)
        {
            req['L']=x-x1;
            count+=x-x1;
        }
        if (y1>y)
        {
            req['U']=y1-y;
            count+=y1-y;
        }
        if (y1<y)
        {
            req['D']=y-y1;
            count+=y-y1;
        }
      
        if (str['D']>=req['D'] && str['L']>=req['L'] && str['U']>=req['U'] && str['R']>=req['R'] )
        {
            cout<<"YES"<<" "<<count<<endl;
            
        }
        else
        {
            cout<<"NO"<<endl;
        }           
    }
}  

}

CENS20G TLE but similar code got accepted :slight_smile:

1 Like


See this
use \n in place of endl to stop flushing your output at every single line as it takes a lot of time for several lines output.

3 Likes

@ssjgz @coder_pc thanks a lot…learnt something new :innocent:

2 Likes

This endl had created a lots of problem, always use \n, with fast i/o

3 Likes

thanks :grinning:

Same happened with me… I will never use endl from now…:pensive:

I have also faced same issue in starting but later on I changed
all possible syntax to fast i/o operations and got AC.

This is my implementation

*#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t–)
{
char st[1000001];
scanf("%s",st);
st[1000000]= ‘\0’;
map<char,int>m;
for(int i=0;st[i]!= ‘\0’;i++)
m[st[i]]++;
int x1,y1;
scanf("%d%d",&x1,&y1);
int q;
scanf("%d",&q);
while(q–)
{
int x2,y2;
scanf("%d%d",&x2,&y2);
int p = x2-x1;
int q = y2-y1;
int lc=0,rc=0,dc=0,uc=0;
if(p < 0 )
lc += abs(x2-x1);

        if(p >= 0 )
                rc += abs(x2-x1);

        if(q < 0 )
                dc += abs(y2-y1);

        if( q >= 0 )
                uc +=  abs(y2-y1);
        if(p < 0  && q >= 0)
        {
            if(lc <= m['L'] &&  uc <= m['U'] )
                    printf("YES %d\n",lc+uc);
            else
                    printf("NO\n");
        }
        if(p < 0  && q < 0)
        {

            if(lc <= m['L'] &&  dc <= m['D'] )
                    printf("YES %d\n",lc+dc);
            else
                   printf("NO\n");

        }
        if(p  >= 0  && q >= 0)
        {
            if(rc <= m['R'] &&  uc <= m['U'] )
                    printf("YES %d\n",rc+uc);
            else
                   printf("NO\n");

        }
        if(p  >= 0  && q < 0)
        {

            if(rc <= m['R'] &&  dc <= m['D'] )
                   printf("YES %d\n",dc+rc);
            else
                   printf("NO\n");
        }
    }

}

}*