PROBLEM LINK : Author : Vibhor Gupta Tester : Vibhor Gupta Editorialist : Vibhor Gupta DIFFICULTY : MediumHard PREREQUISITES : Arrays, Euclid's Distance PROBLEM : Rahul has been given a new task. He has been given N points on the xaxis, X1,X2,...,XN. Now he is being asked Q queries. Each query gives him his position on the xaxis 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 : #include #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[i1]+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
This question is marked "community wiki".
asked 30 Mar '16, 21:57
