SHARE
TWEET

Toi11_cannon O(n + k m log n )

SuitNdtie Apr 26th, 2019 69 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<stdio.h>
  2. #include<utility>
  3. using namespace std;
  4.  
  5. int main()
  6. {
  7.     int n,m,k,len;
  8.     scanf("%d %d %d %d",&n,&m,&k,&len);
  9.     int cannon[n];for(int i = 0 ; i < n ; i ++)scanf("%d",&cannon[i]);
  10.    
  11.     for(int t = 0 ; t < k ; t ++){
  12.        
  13.         int prev = -1;
  14.         int sum = 0;
  15.         for(int i = 0 ; i < m ; i ++){
  16.             int suppos;
  17.             scanf("%d",&suppos);
  18.             int L = -1,R = -1;
  19.             int l = 0 , r = n - 1;
  20.             while(l <= r){ // (R])
  21.                 int m = (l+r)/2;
  22.                 if(cannon[m] <= suppos + len){
  23.                     if(suppos - len <= cannon[m] && cannon[m] <= suppos + len)R = m;
  24.                     l = m + 1;
  25.                 }
  26.                 else{
  27.                     r = m - 1;
  28.                 }
  29.             }
  30.             l = 0 ; r = n - 1;
  31.            
  32.             while(l <= r){  //[L
  33.                 int m = (l+r)/2;
  34.                 if(suppos - len <= cannon[m]){
  35.                     if(suppos - len <= cannon[m] && cannon[m] <= suppos + len)L = m;
  36.                     r = m - 1;
  37.                 }
  38.                 else{
  39.                     l = m + 1;
  40.                 }
  41.             }
  42.             if(L == -1 || R == -1)continue;
  43.             if(L <= prev){
  44.                 sum += R - prev;
  45.             }
  46.             else{
  47.                 sum += R - L + 1;
  48.             }
  49.             prev = R;
  50.         }
  51.         printf("%d\n",sum);
  52.     }
  53.     return 0;
  54. }
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
 
Top