Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- const int INF = 1e9;
- using pii = pair<int,int>;
- int point[1000000];
- int f(vector <pii> event,int n){
- sort(event.begin(),event.end());
- int s = -1, cnt = 0, c = 0;
- for(auto e:event){
- if(e.second == 1){
- if(s == -1) s = e.first;
- c++;
- }
- else
- c--;
- if(s != -1 and c == 0){
- int l = 0, r = n-1, mid, mn = INF, mx = -INF;
- while(l <= r){
- mid = (l+r)/2;
- if(s <= point[mid]){
- mn = min(mn,mid);
- r = mid-1;
- }
- else l = mid+1;
- }
- s = -1;
- if(mn == INF) continue;
- l = 0, r = n-1;
- while(l <= r){
- mid = (l+r)/2;
- if(point[mid] <= e.first-1){
- mx = max(mx,mid);
- l = mid+1;
- }
- else r = mid-1;
- }
- if(mx == -INF) continue;
- cnt += mx-mn+1;
- }
- }
- return cnt;
- }
- int main(){
- int n,m,k,l;
- scanf("%d%d%d%d",&n,&m,&k,&l);
- for(int i=0;i<n;i++) scanf("%d",&point[i]);
- while(k--){
- vector <pii> event;
- int x;
- for(int i=0;i<m;i++){
- scanf("%d",&x);
- if(x-l <0) event.push_back({0,1});
- else event.push_back({x-l,1});
- event.push_back({x+l+1,2});
- }
- printf("%d\n",f(event,n));
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement