Cod sursa(job #1234078)

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

#define NMAX 16005
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];

//Parsare2
class InputReader {
    public:
        InputReader() {}
        InputReader(const char *file_name) {
            input_file = fopen(file_name, "r");
            cursor = 0;
            fread(buffer, SIZE, 1, input_file);
        }
        inline InputReader &operator >>(int &n) {
            while(!isdigit(buffer[cursor]) && buffer[cursor]!='-')
                advance();

            int sgn=1;
            if(buffer[cursor]=='-'){
                sgn=-1;
                advance();
            }

            n = 0;
            while('0' <= buffer[cursor] && buffer[cursor] <= '9') {
                n = n * 10 + buffer[cursor] - '0';
                advance();
            }
            n*=sgn;

            return *this;
        }

    private:
        FILE *input_file;
        static const int SIZE = 1 << 22;
        int cursor;
        char buffer[SIZE];
        inline void advance() {
            ++ cursor;
            if(cursor == SIZE) {
                cursor = 0;
                fread(buffer, SIZE, 1, input_file);
            }
        }
};

int main()
{
    InputReader 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){
        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());

    build(1,setx.size());

    int m=0;
    cin>>m;

    int x1,y1,x2,y2;
    while(m--){
        cin>>x1>>y1>>x2>>y2;

        x1=lower_bound(setx.begin(),setx.end(),x1)-setx.begin()+1;
        x2=upper_bound(setx.begin(),setx.end(),x2)-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;
}