Cod sursa(job #3144826)

Utilizator superffffalexandru radu superffff Data 10 august 2023 19:54:00
Problema Zoo Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.08 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <cctype>
#include <unordered_map>
#include <cmath>
#include <bitset>
#include <set>
#include <string>
#include <cstring>
#include <algorithm>
#include <deque>
#define INF 2140000000
#define MaxT 1000000
#define MaxN 16005
#define MaxM 100005
#define MAX 131072
#define MAXS 300005
using namespace std;
ifstream in("zoo.in");
ofstream out("zoo.out");
int a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,S,t,z,ok,nr,C,xc,yc,Min,w,poz,ans;
struct _Punct{
  int x,y;
};
struct _Query{
   int xin,yin,xfi,yfi;
};
_Punct v[200005];
_Query Q[200005];
vector<int>T[200005];
vector<int>Poz[200005];
map<int,int>M;
int cmp(_Punct k,_Punct h){
     return k.y<h.y;
}
void Build(int node,int left,int right){
   if(left==right){
   for(auto w:Poz[left]){
    T[node].push_back(w);
   }
   }
   else{
    int mid=(left+right)>>1;
    Build(2*node,left,mid);
    Build(2*node+1,mid+1,right);
    int a1=T[2*node].size();
    int b1=T[2*node+1].size();
    int i=0;
    int j=0;
    while(i<a1 && j<b1){
        if(T[2*node][i]<T[2*node+1][j]){
            T[node].push_back(T[2*node][i]);
            i++;
        }
        else{
            T[node].push_back(T[2*node+1][j]);
            j++;
        }
    }
    while(i<a1){
        T[node].push_back(T[2*node][i]);
        i++;
    }
    while(j<b1){
        T[node].push_back(T[2*node+1][j]);
        j++;
    }

   }
}
int cb1(int st,int dr,int val,int i){
   int poz=-1;
   while(st<=dr){
    int l=(st+dr)>>1;
    if(val<=T[i][l]) {dr=l-1; poz=l;}
    if(val>T[i][l]) {st=l+1;}
   }
  return poz;
}
int cb2(int st,int dr,int val,int i){
   int poz=-1;
   while(st<=dr){
    int l=(st+dr)>>1;
    if(val<T[i][l]) {dr=l-1;}
    if(val>=T[i][l]) {st=l+1; poz=l;}
   }
   return poz;
}
void Query(int node,int id,int left,int right){
    if(Q[id].xin<=left && right<=Q[id].xfi){
            if(T[node].size()>0) {
        int stt=cb1(0,T[node].size()-1,Q[id].yin,node);
        int drr=cb2(0,T[node].size()-1,Q[id].yfi,node);
        if(stt>-1 && drr>-1 && stt<=drr){
        ans=ans+(drr-stt+1);
        }
        }
    }
    else{
        int mid=(left+right)>>1;
        if(Q[id].xin<=mid && T[2*node].size()>0){
            Query(2*node,id,left,mid);
        }
        if(Q[id].xfi>=mid+1 && T[2*node+1].size()>0){
            Query(2*node+1,id,mid+1,right);
        }
    }
}
int main()
{
  in>>n;
  for(i=1;i<=n;i++){
     in>>v[i].x>>v[i].y;
     M[v[i].x]=0;
  }
   sort(v+1,v+n+1,cmp);
   in>>m;
  for(i=1;i<=m;i++){
    in>>Q[i].xin>>Q[i].yin>>Q[i].xfi>>Q[i].yfi;
    M[Q[i].xin]=0;
    M[Q[i].xfi]=0;
  }
  k=0;
  for(auto w:M){
    M[w.first]=++k;
  }
  for(i=1;i<=n;i++){
    v[i].x=M[v[i].x];
    Poz[v[i].x].push_back(v[i].y);
  }
  for(i=1;i<=m;i++){
    Q[i].xin=M[Q[i].xin];
    Q[i].xfi=M[Q[i].xfi];
  }
  sort(v+1,v+n+1,cmp);
  Build(1,1,k);
  for(i=1;i<=m;i++){
        ans=0;
        Query(1,i,1,k);
        out<<ans<<'\n';
  }
  return 0;

}