Cod sursa(job #1233914)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 26 septembrie 2014 12:41:11
Problema Zoo Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.78 kb
#include <fstream>
//#include <iostream>
#include <algorithm>
#include <vector>
//#include <map>
#include <set>
#include <cstring>
#include <cctype>
#include <cassert>

#define NMAX 16005
#define MMAX 100005
#define lsb(x) ((x)&(-x))
using namespace std;

int aib[16005];
int marime;

inline void update(int i){
    for(;i<=marime;i+=lsb(i))
        aib[i]++;
}

inline int query(int i){
    int s=0;
    for(;i;i-=lsb(i))
        s+=aib[i];
    return s;
}

int ans[MMAX];

//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');
        ++poz;
    }

    return (semn*rez);
}*/
//End of Parsare

struct operatie
{
    int x,y;

    int tip;
    int poz;
}op[NMAX+4*MMAX];

bool operator<(const operatie &a,const operatie &b){
    if(a.x<b.x)
        return 1;
    if(a.x>b.x)
        return 0;

    return a.tip<b.tip;
}

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

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

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

    int n=0;
    //cit();

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

    set<int> verifx;
    set<int> verify;

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

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

        op[i].poz=i;

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

        if(!verifx.count(op[i].x)){
            setx.push_back(op[i].x);
            verifx.insert(op[i].x);
        }

        if(!verify.count(op[i].y)){
            sety.push_back(op[i].y);
            verify.insert(op[i].y);
        }
    }

    sort(setx.begin(),setx.end());
    sort(sety.begin(),sety.end());

    /*vector<int>::iterator it;
    int i=1;
    hartax[setx[0]]=1;

    for(int j=1;j<setx.size();++j)
        if(setx[j-1]!=setx[j])
            hartax[setx[j]]=++i;

    i=1;
    hartay[sety[0]]=1;

    for(int j=1;j<sety.size();++j)
        if(sety[j-1]!=sety[j])
            hartay[sety[j]]=++i;
    */
    for(int i=1;i<=n;++i){
        //op[i].x=hartax[op[i].x];
        //op[i].y=hartay[op[i].y];
        op[i].x=lower_bound(setx.begin(),setx.end(),op[i].x)-setx.begin()+1;
        op[i].y=lower_bound(sety.begin(),sety.end(),op[i].y)-sety.begin()+1;
    }
    //End of Normalizare

    int m=0;
    cin>>m;
    //m=extract();

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

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

        //itt=hartay.lower_bound(y1);itt--;
        //y1=itt->second;
        y1=lower_bound(sety.begin(),sety.end(),y1)-sety.begin();

        //itt=hartay.upper_bound(y2);itt--;
        //y2=itt->second;
        y2=upper_bound(sety.begin(),sety.end(),y2)-sety.begin();

        //itt=hartax.lower_bound(x1);itt--;
        //x1=itt->second;
        x1=lower_bound(setx.begin(),setx.end(),x1)-setx.begin();

        //itt=hartax.upper_bound(x2);itt--;
        //x2=itt->second;
        x2=upper_bound(setx.begin(),setx.end(),x2)-setx.begin();

        assert(y1 && y1 && x1 && x2);

        //cout<<"am citit "<<x1<<' '<<y1<<' '<<x2<<' '<<y2<<endl;
        if(y1<=y2 && x1<=x2){
            //cout<<query(y1,y2,1,x2-1)-query(y1,y2,1,x1-1)<<'\n';
            op[++poz].poz=i;
            op[poz].tip=1;
            op[poz].x=x2;
            op[poz].y=y2;

            op[++poz].poz=i;
            op[poz].tip=1;
            op[poz].x=x1;
            op[poz].y=y1;

            op[++poz].poz=i;
            op[poz].tip=2;
            op[poz].x=x1;
            op[poz].y=y2;

            op[++poz].poz=i;
            op[poz].tip=2;
            op[poz].x=x2;
            op[poz].y=y1;
        }
    }

    sort(op+1,op+poz+1);

    marime=setx.size();
    for(int i=1;i<=poz;++i)
        if(!op[i].tip)
            update(op[i].y);
        else if(op[i].tip==1)
            ans[op[i].poz]+=query(op[i].y);
        else
            ans[op[i].poz]-=query(op[i].y);

    for(int i=1;i<=m;++i){
        cout<<ans[i]<<'\n';
        assert(ans[i]>=0);
    }

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