Cod sursa(job #2021632)

Utilizator Alex18maiAlex Enache Alex18mai Data 14 septembrie 2017 09:06:42
Problema Zoo Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.68 kb
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

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

/*ifstream cin("input");
ofstream cout("output");*/

struct anim {
    int x;
    int y;
} A[16100];

bool cmp (anim a , anim b){
    if (a.x != b.x){
        return a.x < b.x;
    }
    return a.y < b.y;
}

vector <int> Arb[100000];

void Update (int nod , int st , int dr , int val , int pos){
    if (st == dr){
        Arb[nod].push_back(val);
        return;
    }
    int mij = (st + dr) / 2;
    if (pos <= mij){
        Update(nod * 2, st , mij , val , pos);
    }
    else{
        Update(nod * 2 + 1, mij + 1 , dr , val , pos);
    }
}

void Update_final(int nod , int st , int dr){
    if (st == dr){
        return;
    }
    int mij = (st + dr) / 2;
    Update_final(nod * 2, st , mij);
    Update_final(nod * 2 + 1, mij + 1 , dr);
    /*for (auto x : Arb[nod * 2]){
        Arb[nod].push_back(x);
    }
    for (auto x : Arb[nod * 2 + 1]){
        Arb[nod].push_back(x);
    }
    sort (Arb[nod].begin() , Arb[nod].end());*/
    Arb[nod].resize(Arb[nod * 2].size() + Arb[nod * 2 + 1].size());
    merge (Arb[nod * 2].begin() , Arb[nod * 2].end() ,
           Arb[nod * 2 + 1].begin() , Arb[nod * 2 + 1].end(),
           Arb[nod].begin());
}

void Querry (int nod , int st , int dr , int minx , int maxx , int miny , int maxy , int &s){
    //cout<<"intru"<<'\n';
    if (Arb[nod][Arb[nod].size() - 1] < miny || Arb[nod][0] > maxy){
        return;
    }
    if (A[st].x >= minx && A[dr].x <= maxx ){
        //caut binar pos y mai mare sau egal cu miny
        // si y mai mic sau egal cu xmax
        //1. caut mai mic
        int ymic = -1;
        int ST = 0;
        int DR = Arb[nod].size() - 1;
        while(ST <= DR){
            int mij = (ST + DR) / 2;
            if (miny <= Arb[nod][mij]){
                ymic = mij;
                //cout<<"gasit mic "<<ymic<<'\n';
                if (ST == DR){
                    break;
                }
                DR = mij;
            }
            else{
                ST = mij + 1;
            }
        }
        //2. caut mai mare
        int ymare = -1;
        ST = 0;
        DR = Arb[nod].size() - 1;
        while(ST <= DR){
            int mij = (ST + DR) / 2;
            if (maxy >= Arb[nod][mij]){
                ymare = mij;
                //cout<<"gasit mare "<<ymare<<'\n';
                ST = mij + 1;
            }
            else{
                if (ST == DR){
                    break;
                }
                DR = mij;
            }
        }
        if (ymic == -1 || ymare == -1 || ymare < ymic){
            return;
        }
        s += ymare - ymic + 1;
        //cout<<"adaug "<<" "<<ymare<<" "<<ymic<<" "<<ymare - ymic + 1<<'\n';
        return;
    }
    if (st == dr){
        return;
    }
    int mij = (st + dr) / 2;
    if (minx <= A[mij].x){
        Querry(nod * 2 , st , mij , minx, maxx , miny , maxy , s);
    }
    if (maxx > A[mij].x){
        Querry(nod * 2 + 1 , mij + 1 , dr , minx, maxx , miny , maxy , s);
    }
}

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin>>n;
    for (int i=1; i<=n; i++){
        cin>>A[i].x>>A[i].y;
    }
    sort (A + 1 , A + n + 1 , cmp);
    /*for (int i=1; i<=n; i++){
        cout<<A[i].x<<" "<<A[i].y<<'\n';
    }*/

    for (int i=1; i<=n; i++){
        Update(1 , 1 , n , A[i].y , i);
    }
    Update_final(1 , 1 , n);
    /*for (auto x : Arb[1]){
        cout<<x<<" ";
    }*/
    int m;
    cin>>m;
    for (int i=1; i<=m; i++){
        int x1 , y1 , x2 , y2;
        cin>>x1>>y1>>x2>>y2;
        int s = 0;
        Querry (1 , 1 , n, x1 , x2 , y1 , y2 , s);
        //cout<<'\n';
        cout<<s<<'\n';
    }
    return 0;
}