Hackerrank Modular Range Queries

Can this code be optimized in any way?

Some of the obvious points:

Remove unnecessary #include statements

Your code doesn't use any stuff from these headers

#include <cmath>
#include <cstdio>
#include <vector>
#include <algorithm>

So you can remove them.

Don't use using namespace std;

That's generally considered bad practice.

Rather use

using std::cout;
using std::cin;

if you want to avoid typing these out.

Use meaningful variable names

Variable names like

int n,q;
int A[n];

don't tell anything about their semantics.

Standard C++ doesn't support VLA's

Code like

int A[n];

isn't portable. Variable Length Arrays aren't supported by the current c++ standard.

Use

std::vector A(n);

instead to create a dynamically sized array.

Check for successful and valid input

cin>>a>>b>>x>>y;

You never check if the above statement succeeded before proceeding to apply the algorithm.

Better do something like

if(!(cin>>a>>b>>x>>y)) {
    std::cout << "Bad input encountered!" << std::endl;
    return 1;
}

Since

t%x

may segfault when x is zero, you should at east have an assert:

std::assert(x);
if(t%x==y) { // ...
}

Always use braces for scoped blocks

for(int i=0;i<n;i++)
    cin>>A[i];

should be

for(int i=0;i<n;i++) { // <<<<<<<
    cin>>A[i];
} // <<<<<<<<

Missing the braces makes that code error prone for changes. It's always better to clarify the scope with conditional or loop statements.

Use prefix incrment (decrement) if you don't need to preserve the previous value

Instead of

for(int i=a;i<=b;i++)
c++;

use

for(int i=a;i<=b;++i)
++c;

You obviously don't need the old value preserved by the postfix increment operations.

Performance of formatted text extraction

The values of of n,q,a,x,y,b are ranging from 1 to 40000. so it gets the timeout therefore it needs to further optimised

As for your performance concerns:

Formatted text extraction in c++ is costly. You may get a performance improvement just using scanf() in this case.

While

cin>>a>>b>>x>>y;

applies four function calls

scanf("%d %d %d %d",a,b,x,y);

would be only one call. Also the internal implementation of the formatted text extraction syntax boils down to some scanf() like functions for most of the c++ compilers anyways.

You are using brute force approach to solve the problem, but with given input constraints, your solution is more likely to time out during system test. This can be solved by segment trees or binary indexed trees which can answer queries in O(logn) time, and for q queries, complete time complexity would be O(q.logn). This will easily pass the final system test.

Basic operations supported by segment tree are : 1. updating single element 2. updating range of elements 3. querying information about range of elements.

Reference : http://letuskode.blogspot.in/2013/01/segtrees.html