fork download
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. using namespace std;
  4. int main(){
  5. int n,x,q;
  6. cin>>n>>q;
  7. int a[1000001],b[1000001],mod=7630367;
  8. //initialize array a,b with 0
  9. for(int i=0;i<1000001;i++) a[i]=b[i]=0;
  10. for(int i=0;i<n;i++){
  11. cin>>x;
  12. //mark the position x+1
  13. //so as to increase the distance of the point
  14. //while moving to the right
  15. // similarly for x-1 for other direction
  16. a[x+1]++;
  17. b[x-1]++;
  18. }
  19. //during update we remember the previous update
  20. //and update the distance of current position with both the updates
  21. ll upd=0;
  22. for(int i=1;i<1000001;i++){
  23. //upd changed
  24. upd=(a[i]+upd)%mod;
  25. a[i]=(a[i-1]+upd)%mod;
  26. }
  27. upd=0;
  28. for(int i=1000001-2;i>=0;i--){
  29. upd=(b[i]+upd)%mod;
  30. b[i]=(b[i+1]+upd)%mod;
  31. }
  32. while(q--){
  33. cin>>x;
  34. cout<<(a[x]+b[x])%mod<<endl;
  35. }
  36. }
  37.  
Success #stdin #stdout 0.09s 11152KB
stdin
3 2
1 3 5
3
4
stdout
4
5