Cod sursa(job #3365110)

Utilizator TudorMitMituca Tudor TudorMit Data 16 septembrie 2026 21:46:02
Problema Zoo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.67 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

ifstream cin("zoo.in");
ofstream cout("zoo.out");

struct punct{
    long long x,y;
};

struct query{
    long long x,y;
    int val,semn;
};

vector<punct>animale;
vector<query>v;

long long aib[200005];
long long rez[100005];

bool comp1(punct a,punct b){
    return a.x<b.x;
}

bool comp2(query a,query b){
    return a.x<b.x;
}

void upd(int poz,int val,int n){
    for(int i=poz;i<=n;i+=i&-i)
        aib[i]+=val;
}

long long qr(int poz){
    long long s=0;
    for(int i=poz;i>0;i-=i&-i)
        s+=aib[i];
    return s;
}

int main(){
    int n,m,p=0,poz;
    cin>>n;
    for(int i=1;i<=n;i++){
        long long x,y;
        cin>>x>>y;
        animale.push_back({x,y});
    }
    vector<long long>vy;
    for(auto p:animale)
        vy.push_back(p.y);
    sort(vy.begin(),vy.end());
    vy.erase(unique(vy.begin(),vy.end()),vy.end());
    sort(animale.begin(),animale.end(),comp1);
    cin>>m;
    for(int i=1;i<=m;i++){
        long long x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        v.push_back({x2,y2,i,1});
        v.push_back({x1-1,y2,i,-1});
        v.push_back({x2,y1-1,i,-1});
        v.push_back({x1-1,y1-1,i,1});
    }
    sort(v.begin(),v.end(),comp2);
    for(auto q:v){
        while(p<n && animale[p].x<=q.x){
            poz=lower_bound(vy.begin(),vy.end(),animale[p].y)-vy.begin()+1;
            upd(poz,1,vy.size());
            p++;
        }
        poz=upper_bound(vy.begin(),vy.end(),q.y)-vy.begin();
        rez[q.val]+=q.semn*qr(poz);
    }
    for(int i=1;i<=m;i++)
        cout<<rez[i]<<"\n";
    return 0;
}