Cod sursa(job #2900677)

Utilizator vladdobro07vladdd vladdobro07 Data 11 mai 2022 22:28:35
Problema Ograzi Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.86 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream cin("ograzi.in");
ofstream cout("ograzi.out");
const int nmax=50000;
int n,m,w,h,x,y,maxx=0,sol=0;
pair<int,int>v[nmax+3],v1[nmax+3];
int binxl(int st,int dr,int x) {
        st=max(st,0);
        dr=min(dr,maxx);
        int mid,last=-1;
        while(st<=dr) {
                mid=(st+dr)/2;
                if(v[mid].first>=x) {
                        last=mid;
                        dr=mid-1;
                } else if(v[mid].first<x)
                                st=mid+1;
        }
        return last;
}
int binyl(int st,int dr,int x) {
        st=max(st,0);
        dr=min(dr,maxx);
        int mid,last=-1;
        while(st<=dr) {
                mid=(st+dr)/2;
                if(v1[mid].first>=x) {
                        last=mid;
                        dr=mid-1;
                } else if(v1[mid].first<x)
                                st=mid+1;
        }
        return last;
}
int query(int x,int y) {
        if(binxl(0,n,x-w+1)!=-1&&binyl(0,n,y-h+1)!=-1&&(binyl(0,n,y-h+1)-binxl(0,n,x-w+1)>=-1)&&(binyl(0,n,y-h+1)-binxl(0,n,x-w+1)<=1))
                sol++;
        //cout<<x<<" "<<y<<" "<<x-w<<" "<<y-h<<" "<<binxl(0,n,x-w+1)<<" "<<binyl(0,n,y-h+1)<<'\n';
}
int main() {
        cin>>n>>m>>h>>w;
        for(int i=1; i<=n; i++) {
                cin>>v[i].second>>v[i].first;
                v1[i].first=v[i].second;
                v1[i].second=v[i].first;
                maxx=max(maxx,max(v[i].first,v[i].second));
        }
        sort(v+1,v+n+1);
        sort(v1+1,v1+n+1);
        //for(int i=1; i<=n; i++)
                //cerr<<v[i].first<<" "<<v[i].second<<", "<<v1[i].first<<" "<<v1[i].second<<'\n';
        for(int i=1; i<=m; i++) {
                cin>>y>>x;
                query(x,y);
        }
        cout<<sol;
        return 0;
}