PROBLEM LINK :
Author : Vibhor Gupta
Tester : Vibhor Gupta
Editorialist : Vibhor Gupta
DIFFICULTY :
Medium-Hard
PREREQUISITES :
Arrays, Euclid’s Distance
PROBLEM :
Rahul has been given a new task.
He has been given N points on the x-axis, X1,X2,…,XN.
Now he is being asked Q queries. Each query gives him his position on the x-axis X, and asks him the sum of distances from his position and the N points.
As the sum can be quite large, he has been told to print the answer modulo 7630367.
He has written a program to calculate every query, but it seems to be giving him vague answers.
Flawed Code :
#define ll long long
using namespace std;
int main(){
int n,x,q;
cin>>n>>q;
int a[n+1],b[n+1],mod=7630367;
for(int i=0;i!=n;i++){
cin>>x;
a[x]++;b[x]++;}
ll upd=0;
for(int i=0;i!=n+1;i++){
upd=a[i]%mod;a[i]=(a[i-1]+upd)%mod;}
upd=0;
for(int i=n;i>=0;i–){
upd=b[i]%mod;b[i]=(b[i+1]+upd)%mod;}
while(q–){cin>>x;printf("%lld",(a[x]+b[x])%mod);}}
EXPLANATION :
This question used a small trick to calculate the distances for each point from either sides.
The corrected code can be view at, Corrected Solution