SHARE
TWEET

Untitled

a guest Aug 23rd, 2019 67 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top