Advertisement
Guest User

Untitled

a guest
Feb 25th, 2018
85
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.43 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define ll long long
  6.  
  7. vector < ll > arr ;
  8.  
  9. #define MOD 1000000007
  10.  
  11. ll bigmod (ll b, ll p)
  12. {
  13.  
  14. if ( p== 0 ) return 1 ;
  15. if ( p % 2 == 0 )
  16. {
  17. ll y = bigmod ( b, p / 2 )%MOD;
  18. return ( y * y ) % MOD;
  19. }
  20. else
  21. {
  22.  
  23. return ( b * bigmod ( b, p - 1 )%MOD ) % MOD;
  24. }
  25. }
  26.  
  27. map<ll,bool>mp;
  28.  
  29. int main()
  30. {
  31. freopen("input/input09.txt","r",stdin);
  32. freopen("output/output09.txt","w",stdout);
  33.  
  34. int n,q;
  35. cin >> n >>q ;
  36. assert(2<=n && n<=100000);
  37. for( int i = 0 ; i < n ; i ++ )
  38. {
  39. ll x, y ;
  40. cin >> x >> y ;
  41. assert(-1000000000<=x && x<=1000000000);
  42. assert(-1000000000<=y && y<=1000000000);
  43. assert(mp[x]==0);
  44. mp[x]=1;
  45. arr.push_back(x);
  46. }
  47. sort(arr.begin(),arr.end());
  48. ll ans = 0 ;
  49. while(q--)
  50. {
  51. int l, r ;
  52. cin >> l >> r ;
  53. assert(-1000000000<=l && l<=1000000000);
  54. assert(-1000000000<=r && r<=1000000000);
  55. if (l >=r )
  56. {
  57. ans = 0 ;
  58.  
  59. }
  60. else
  61. {
  62. ll x = lower_bound(arr.begin(),arr.end(),l) - arr.begin();
  63. ll y = upper_bound(arr.begin(),arr.end(),r) - arr.begin();
  64. ll z=y-x-2;
  65. if(z>1)
  66. ans = bigmod(2,z) - 2 ;
  67. }
  68.  
  69. cout << (ans+MOD)%MOD << endl;
  70. }
  71.  
  72. return 0;
  73. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement