Cod sursa(job #1234062)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 26 septembrie 2014 17:38:10
Problema Zoo Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.71 kb
#include <fstream>
#include <iostream>
#include <algorithm>
#include <vector>
#include <cassert>

#define NMAX 36005
using namespace std;

struct nod{
    int st;
    int dr;
    vector<int> cells;

    nod(): st(0), dr(0) {}
}arb[4*NMAX];

vector<int> sorted[NMAX];

void build(int st,int dr,int nod=1){
    arb[nod].st=st;arb[nod].dr=dr;

    if(st==dr){
        arb[nod].cells=sorted[st];
        return;
    }

    int mijl=(st+dr)>>1;
    build(st,mijl,nod<<1);
    build(mijl+1,dr,(nod<<1)+1);

    arb[nod].cells.resize(arb[nod<<1].cells.size()+arb[(nod<<1)+1].cells.size());
    merge(arb[nod<<1].cells.begin(),arb[nod<<1].cells.end(),arb[(nod<<1)+1].cells.begin(),arb[(nod<<1)+1].cells.end(),arb[nod].cells.begin());
}

int ans=0;
void query(int st,int dr,int y1,int y2,int nod=1){
    if(arb[nod].st==st && arb[nod].dr==dr){
        int val=(upper_bound(arb[nod].cells.begin(),arb[nod].cells.end(),y2)-lower_bound(arb[nod].cells.begin(),arb[nod].cells.end(),y1));
        if(val>0)
            ans+=val;
        return;
    }

    int mijl=(arb[nod].st+arb[nod].dr)>>1;
    if(dr<=mijl)
        query(st,dr,y1,y2,nod<<1);
    else if(st>mijl)
        query(st,dr,y1,y2,(nod<<1)+1);
    else{
        query(st,mijl,y1,y2,nod<<1);
        query(mijl+1,dr,y1,y2,(nod<<1)+1);
    }
}

struct punct{
    int x,y;
}v[NMAX];

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

    vector<int> toatex;

    int n=0;
    cin>>n;

    for(int i=1;i<=n;++i){
        cin>>v[i].x>>v[i].y;
        toatex.push_back(v[i].x);
    }

    sort(toatex.begin(),toatex.end());

    vector<int> setx;

    setx.push_back(toatex[0]);

    for(int i=1;i<n;++i)
        if(toatex[i]!=toatex[i-1])
            setx.push_back(toatex[i]);

    for(int i=1;i<=n;++i){
        assert(find(setx.begin(),setx.end(),v[i].x)!=setx.end());
        v[i].x=find(setx.begin(),setx.end(),v[i].x)-setx.begin()+1;

        sorted[v[i].x].push_back(v[i].y);
    }

    for(int i=1;i<=setx.size();++i)
        sort(sorted[i].begin(),sorted[i].end());

    assert(setx.size()>0);
    build(1,setx.size());

    int m=0;
    cin>>m;

    int x1,y1,x2,y2;

    vector<int>::iterator it;
    while(m--){
        cin>>x1>>y1>>x2>>y2;

        x1=lower_bound(setx.begin(),setx.end(),x1)-setx.begin()+1;

        it=upper_bound(setx.begin(),setx.end(),x2);
        if(it==setx.begin()){
            cout<<"0\n";
            continue;
        }

        x2=it-setx.begin();

        if(x1>x2){
            cout<<"0\n";
            continue;
        }

        ans=0;query(x1,x2,y1,y2);
        cout<<ans<<'\n';
    }

    cin.close();
    cout.close();
    return 0;
}