Toi11_cannon O(n + k m log n )

#include<stdio.h>
#include<utility>
using namespace std;

int main()
{
    int n,m,k,len;
    scanf("%d %d %d %d",&n,&m,&k,&len);
    int cannon[n];for(int i = 0 ; i < n ; i ++)scanf("%d",&cannon[i]);

    for(int t = 0 ; t < k ; t ++){

        int prev = -1;
        int sum = 0;
        for(int i = 0 ; i < m ; i ++){
            int suppos;
            scanf("%d",&suppos);
            int L = -1,R = -1;
            int l = 0 , r = n - 1;
            while(l <= r){ // (R])
                int m = (l+r)/2;
                if(cannon[m] <= suppos + len){
                    if(suppos - len <= cannon[m] && cannon[m] <= suppos + len)R = m;
                    l = m + 1;
                }
                else{
                    r = m - 1;
                }
            }
            l = 0 ; r = n - 1;

            while(l <= r){  //[L
                int m = (l+r)/2;
                if(suppos - len <= cannon[m]){
                    if(suppos - len <= cannon[m] && cannon[m] <= suppos + len)L = m;
                    r = m - 1;
                }
                else{
                    l = m + 1;
                }
            }
            if(L == -1 || R == -1)continue;
            if(L <= prev){
                sum += R - prev;
            }
            else{
                sum += R - L + 1;
            }
            prev = R;
        }
        printf("%d\n",sum);
    }
    return 0;
}