Cod sursa(job #2021603)

Utilizator Alex18maiAlex Enache Alex18mai Data 13 septembrie 2017 23:53:09
Problema Zoo Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.69 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[70000];

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){
    if (A[st].x >= minx && A[dr].x <= maxx && Arb[nod][0] >= miny && Arb[nod][Arb[nod].size() - 1] <= maxy ){
        s += Arb[nod].size();
        /*for (auto x : Arb[nod]){
            cout<<x<<" ";
        }*/
        return;
    }
    if (st == dr){
        return;
    }
    int mij = (st + dr) / 2;
    if (minx < A[mij].x  || (minx == A[mij].x && miny >= Arb[nod][0] && maxy > Arb[nod][Arb[nod].size() - 1])){
        Querry(nod * 2 , st , mij , minx, maxx , miny , maxy , s);
    }
    if (maxx > A[mij].x || (maxx == A[mij].x && miny < Arb[nod][0] && maxy <= Arb[nod][Arb[nod].size() - 1])){
        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;
}