Advertisement
YEZAELP

TOI11: Cannons at the Fort

Jul 11th, 2020
102
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.57 KB | None
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int INF = 1e9;
  5. using pii = pair<int,int>;
  6. int point[1000000];
  7.  
  8. int f(vector <pii> event,int n){
  9.  
  10.     sort(event.begin(),event.end());
  11.  
  12.     int s = -1, cnt = 0, c = 0;
  13.     for(auto e:event){
  14.  
  15.         if(e.second == 1){
  16.             if(s == -1) s = e.first;
  17.             c++;
  18.         }
  19.         else
  20.             c--;
  21.  
  22.         if(s != -1 and c == 0){
  23.             int l = 0, r = n-1, mid, mn = INF, mx = -INF;
  24.             while(l <= r){
  25.                 mid = (l+r)/2;
  26.                 if(s <= point[mid]){
  27.                     mn = min(mn,mid);
  28.                     r = mid-1;
  29.                 }
  30.                 else l = mid+1;
  31.             }
  32.             s = -1;
  33.             if(mn == INF) continue;
  34.             l = 0, r = n-1;
  35.             while(l <= r){
  36.                 mid = (l+r)/2;
  37.                 if(point[mid] <= e.first-1){
  38.                     mx = max(mx,mid);
  39.                     l = mid+1;
  40.                 }
  41.                 else r = mid-1;
  42.             }
  43.             if(mx == -INF) continue;
  44.             cnt += mx-mn+1;
  45.         }
  46.  
  47.     }
  48.     return cnt;
  49. }
  50. int main(){
  51.  
  52.     int n,m,k,l;
  53.     scanf("%d%d%d%d",&n,&m,&k,&l);
  54.  
  55.     for(int i=0;i<n;i++) scanf("%d",&point[i]);
  56.  
  57.     while(k--){
  58.         vector <pii> event;
  59.         int x;
  60.         for(int i=0;i<m;i++){
  61.             scanf("%d",&x);
  62.             if(x-l <0) event.push_back({0,1});
  63.             else event.push_back({x-l,1});
  64.             event.push_back({x+l+1,2});
  65.         }
  66.         printf("%d\n",f(event,n));
  67.     }
  68.  
  69.     return 0;
  70. }
Advertisement
RAW Paste Data Copied
Advertisement