• Sign Up
• Login
• API
• FAQ
• Tools
• Archive
SHARE
TWEET # Toi11_cannon O(n + k m log n ) SuitNdtie  Apr 26th, 2019 73 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.

Top