Advertisement
Guest User

Untitled

a guest
Aug 23rd, 2019
83
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.41 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define LL long long
  3. #define endl "\n"
  4.  
  5. using namespace std ;
  6.  
  7. //
  8. template < typename T >
  9.  
  10. inline T read( T &x )
  11. {
  12.  
  13. x = 0 ;
  14.  
  15. int f = 0 ;
  16.  
  17. char ch = getchar() ;
  18.  
  19. while( ch < '0' || ch > '9' ) {
  20.  
  21. f |= ( ch == '-' ) , ch = getchar() ;
  22.  
  23. }
  24.  
  25. while( ch >= '0' && ch <= '9' ) {
  26.  
  27. x = ( x << 1 ) + ( x << 3 ) + ch - '0' , ch = getchar() ;
  28.  
  29. }
  30.  
  31. return x = f ? -x:x ;
  32.  
  33. }
  34. //
  35.  
  36. int sz ;
  37.  
  38. int lobo( int key , int female[] , int L , int R )
  39. {
  40.  
  41. int low = 0 , high = sz-1 , ans = -1 ;
  42.  
  43. while( low <= high ) {
  44.  
  45. int mid = low + (high-low)/2 ;
  46.  
  47. if( female[mid]+key < L ) {
  48.  
  49. low = mid+1 ;
  50.  
  51. }
  52.  
  53. else if( female[mid]+key >= L ) {
  54.  
  55. if( female[mid]+key <= R ) {
  56.  
  57. ans = mid ;
  58.  
  59. }
  60.  
  61. high = mid-1 ;
  62.  
  63. }
  64.  
  65. }
  66.  
  67. return ans ;
  68.  
  69. }
  70.  
  71. int hibo( int key , int female[] , int L , int R )
  72. {
  73.  
  74. int ans = -1 , high = sz-1 , low = 0 ;
  75.  
  76. while( low <= high ) {
  77.  
  78. int mid = low + (high-low)/2 ;
  79.  
  80. if( female[mid] + key > R ) {
  81.  
  82. high = mid-1 ;
  83.  
  84. }
  85.  
  86. else {
  87.  
  88. low = mid+1 ;
  89.  
  90. if( female[mid]+key >= L ) ans = mid ;
  91.  
  92. }
  93.  
  94. }
  95.  
  96. return ans ;
  97.  
  98. }
  99.  
  100. void solve( void )
  101. {
  102.  
  103. int N , M ;
  104.  
  105. cin >> N >> M ;
  106.  
  107. int male[N] ;
  108.  
  109. int fe[M] ;
  110.  
  111. sz = M ;
  112.  
  113. for( int i = 0 ; i < N ; i++ ) cin >> male[i] ;
  114.  
  115. for( int i = 0 ; i < M ; i++ ) cin >> fe[i] ;
  116.  
  117. int L , R ;
  118.  
  119. cin >> L >> R ;
  120.  
  121. sort( male , male+N ) ;
  122.  
  123. sort( fe , fe + M ) ;
  124.  
  125. int cnt = 0 ;
  126.  
  127. for( int i = 0 ; i < N ; i++ ) {
  128.  
  129. int x = lobo( male[i] , fe , L , R ) ;
  130.  
  131. int y = hibo( male[i] , fe , L , R ) ;
  132.  
  133. if( x == -1 || y == -1 ) continue ;
  134.  
  135. // cout << "male: " << male[i] << " x: " << x << " y: " << y << endl ;
  136.  
  137. cnt += (y-x+1) ;
  138.  
  139. }
  140.  
  141. cout << cnt << endl ;
  142.  
  143. }
  144.  
  145. int main( void )
  146.  
  147. {
  148.  
  149. //ios_base::sync_with_stdio( false ) ; cin.tie( NULL ) ; cout.tie( NULL ) ;
  150.  
  151. #ifndef ONLINE_JUDGE
  152. freopen( "input.txt" , "r" , stdin ) ;
  153. freopen( "output.txt" , "w" , stdout ) ;
  154. #endif
  155.  
  156. if( 0 ) {
  157.  
  158. int t = 100 ;
  159.  
  160. for( int i = 1 ; i <= t ; i++ ) solve() ;
  161.  
  162. }
  163.  
  164. else {
  165.  
  166. solve() ;
  167.  
  168. }
  169.  
  170. #ifndef ONLINE_JUDGE
  171. cout << "\nTime Elapsed: " << 1.0*clock()/CLOCKS_PER_SEC << " sec\n" ;
  172. #endif
  173.  
  174. return 0 ;
  175.  
  176. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement