Cod sursa(job #1233966)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 26 septembrie 2014 14:46:10
Problema Zoo Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 6.23 kb
#include <fstream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
#include <cstring>
#include <cctype>
#include <utility>

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

short int aib[16005];
short int marime;

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

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

short int ans[MMAX];

//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;
        }

        inline InputReader &operator >>(short int &n) {
            while(!isdigit(buffer[cursor]) && buffer[cursor]!='-')
                advance();

            short 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);
            }
        }
};
//End of Parsare2

struct operatie
{
    int x,y1,y2;

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

bool operator<(const operatie &a,const operatie &b){
    if(a.x==b.x)
        return a.tip<b.tip;
    return a.x<b.x;
}

InputReader cin("zoo.in");

inline int cb(vector<int> &v,int x){ //Indicele ultimului element din vector <=x
    /*int st=0;
    int dr=v.size()-1;
    int mijl=(st+dr)>>1;
    int ans=0;

    while(st<=dr){
        if(v[mijl]<=x){
            ans=mijl;
            st=mijl+1;
        }
        else
            dr=mijl-1;

        mijl=(st+dr)>>1;
    }

    return ans;*/

    /*int i=1;
    for(;i<=v.size();i<<=1);

    int j=0;
    for(;i;i>>=1)
        if(v[j+i-1]<=x)
            j+=i;

    return j;*/

    int i, step;
    for (step = 1; step < v.size(); step <<= 1);
    for (i = 0; step; step >>= 1)
        if (i + step < v.size() && v[i + step] <= x)
           i += step;
    return i;
}

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

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

    ofstream cout("zoo.out");

    vector<int> setx,sety;

    short int n=0;
    //cit();

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

    vector<pair<int,int> > verifx;
    vector<pair<int,int> > verify;

    //Normalizare
    verifx.push_back(make_pair(-2000000005,0));
    verifx.push_back(make_pair(2000000005,0));
    verify.push_back(make_pair(-2000000005,0));
    verify.push_back(make_pair(2000000005,0));

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

        op[i].poz=i;

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

        //if(!verify.count(op[i].y)){
            verify.push_back(make_pair(op[i].y1,i));
        //    verify.insert(op[i].y);
        //}
    }

    sort(verifx.begin(),verifx.end());
    sort(verify.begin(),verify.end());

    setx.push_back(verifx[0].first);
    sety.push_back(verify[0].first);

    for(short int i=1;i<verifx.size();++i){
        if(verifx[i].first!=verifx[i-1].first)
            setx.push_back(verifx[i].first);

        if(verify[i].first!=verify[i-1].first)
            sety.push_back(verify[i].first);

        op[verifx[i].second].x=setx.size();
        op[verify[i].second].y1=sety.size();
    }

    //for(int i=1;i<=n;++i){
    //    op[i].x=lower_bound(setx.begin(),setx.end(),op[i].x)-setx.begin()+1;
    //    op[i].y1=lower_bound(sety.begin(),sety.end(),op[i].y1)-sety.begin()+1;
    //}
    //End of Normalizare

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

    int x1,y1,x2,y2;

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

        //x1=lower_bound(setx.begin(),setx.end(),x1)-setx.begin();
        x1=cb(setx,x1-1)+1;
        //x2=upper_bound(setx.begin(),setx.end(),x2)-setx.begin();
        x2=cb(setx,x2)+1;

        //y1=lower_bound(sety.begin(),sety.end(),y1)-sety.begin();
        y1=cb(sety,y1-1)+1;
        //y2=upper_bound(sety.begin(),sety.end(),y2)-sety.begin();
        y2=cb(sety,y2)+1;

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

        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].y2=y2;
            op[poz].y1=y1;

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

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

    marime=sety.size();
    for(int i=1;i<=poz;++i)
        if(!op[i].tip)
            update(op[i].y1);
        else{
            ans[op[i].poz]+=query(op[i].y2);
            ans[op[i].poz]-=query(op[i].y1);
        }

    for(int i=1;i<=m;++i)
        cout<<ans[i]<<'\n';

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