Cod sursa(job #1233566)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 25 septembrie 2014 18:35:24
Problema Zoo Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.85 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <cstring>
#include <cassert>
#include <cctype>

#define NMAX 16005
using namespace std;

struct variant{
    int sum;
    int ttime;
    int poz_st;
    int poz_dr;

    variant(int sum=0,int ttime=0,int poz_st=0,int poz_dr=0): sum(sum), ttime(ttime), poz_st(poz_st), poz_dr(poz_dr) {}
};

struct node{
    int st;
    int dr;
    vector<variant> ttimes;

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

void build(int st,int dr,int nod){
    arb[nod].st=st;arb[nod].dr=dr;
    arb[nod].ttimes.push_back(variant(0,0,0,0));

    if(st==dr)
        return;

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

int ttime;
void update(int unde,int nod,int poz){
    arb[nod].ttimes[poz].sum++;
    if(arb[nod].st==arb[nod].dr)
        return;

    int mijl=(arb[nod].st+arb[nod].dr)>>1;
    if(unde<=mijl){
        if(arb[nod<<1].ttimes[arb[nod<<1].ttimes.size()-1].ttime!=ttime){
            arb[nod<<1].ttimes.push_back(arb[nod<<1].ttimes[arb[nod<<1].ttimes.size()-1]);
            arb[nod<<1].ttimes[arb[nod<<1].ttimes.size()-1].ttime=ttime;
            arb[nod].ttimes[poz].poz_st=arb[nod<<1].ttimes.size()-1;
        }
        update(unde,nod<<1,arb[nod].ttimes[poz].poz_st);
    }
    else{
        if(arb[(nod<<1)+1].ttimes[arb[(nod<<1)+1].ttimes.size()-1].ttime!=ttime){
            arb[(nod<<1)+1].ttimes.push_back(arb[(nod<<1)+1].ttimes[arb[(nod<<1)+1].ttimes.size()-1]);
            arb[(nod<<1)+1].ttimes[arb[(nod<<1)+1].ttimes.size()-1].ttime=ttime;
            arb[nod].ttimes[poz].poz_dr=arb[(nod<<1)+1].ttimes.size()-1;
        }
        update(unde,(nod<<1)+1,arb[nod].ttimes[poz].poz_dr);
    }
}

int query(int st,int dr,int nod,int poz){
    if(arb[nod].st==st && arb[nod].dr==dr)
        return arb[nod].ttimes[poz].sum;

    int mijl=(arb[nod].st+arb[nod].dr)>>1;
    if(dr<=mijl)
        return query(st,dr,nod<<1,arb[nod].ttimes[poz].poz_st);
    else if(st>mijl)
        return query(st,dr,(nod<<1)+1,arb[nod].ttimes[poz].poz_dr);
    else
        return (query(st,mijl,nod<<1,arb[nod].ttimes[poz].poz_st)+query(mijl+1,dr,(nod<<1)+1,arb[nod].ttimes[poz].poz_dr));
}

struct point{
    int x;
    int y;
}v[NMAX];

bool operator<(const point &a,const point &b){
    return a.x<b.x;
}

set<int> setx,sety;
map<int,int> hartax;
map<int,int> hartay;

//Parsare
ifstream cin("zoo.in");

char sir[6496005];
int lung,poz;

inline void cit(){
    cin.get(sir+1,6496005,'#');
    lung=strlen(sir+1);
    poz=1;
}

inline int extract(){
    while(poz<=lung && (!isdigit(sir[poz]) && sir[poz]!='-'))
        poz++;

    int semn=1;
    if(sir[poz]=='-'){
        semn=-1;
        poz++;
    }

    int rez=0;
    while(poz<=lung && isdigit(sir[poz])){
        rez*=10;
        rez+=(sir[poz++]-'0');
    }

    return (semn*rez);
}

//End of Parsare

int main()
{
    ios_base::sync_with_stdio(false);

    ofstream cout("zoo.out");

    int n=0;
    cit();

    //cin>>n;
    n=extract();

    //Normalizare
    setx.insert(-2000000005);
    setx.insert(2000000005);
    sety.insert(-2000000005);
    sety.insert(2000000005);

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

        setx.insert(v[i].x);
        sety.insert(v[i].y);
    }

    set<int>::iterator it;
    int i=1;
    for(it=setx.begin();it!=setx.end();it++,i++)
        hartax[*it]=i;

    i=1;
    for(it=sety.begin();it!=sety.end();it++,i++)
        hartay[*it]=i;

    sort(v+1,v+n+1);
    for(int i=1;i<=n;i++){
        v[i].x=hartax[v[i].x];
        v[i].y=hartay[v[i].y];
    }
    //End of Normalizare

    build(1,hartay.size(),1);

    for(int i=1;i<=n;i++){
        ttime=v[i].x;

        if(arb[1].ttimes[arb[1].ttimes.size()-1].ttime!=ttime){
            arb[1].ttimes.push_back(arb[1].ttimes[arb[1].ttimes.size()-1]);
            arb[1].ttimes[arb[1].ttimes.size()-1].ttime=ttime;
        }
        update(v[i].y,1,arb[1].ttimes.size()-1);
    }

    int m=0;
    //cin>>m;
    m=extract();
    assert(m<=70000);

    int x1,y1,x2,y2;
    map<int,int>::iterator itt;

    for(int i=1;i<=m;i++){
        //cin>>x1>>y1>>x2>>y2;
        x1=extract();
        y1=extract();
        x2=extract();
        y2=extract();

        y1=hartay.lower_bound(y1)->second;
        itt=hartay.upper_bound(y2);itt--;
        y2=itt->second;

        itt=hartax.lower_bound(x1);itt--;
        x1=itt->second;

        itt=hartax.upper_bound(x2);itt--;
        x2=itt->second;

        if(y1>y2 || x1>x2)
            cout<<"0\n";
        else
            cout<<query(y1,y2,1,x2-1)-query(y1,y2,1,x1-1)<<'\n';
    }

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