Cod sursa(job #1833417)

Utilizator mariakKapros Maria mariak Data 22 decembrie 2016 12:10:14
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.59 kb
#include <bits/stdc++.h>
#define NMAX 16002
#define MMAX 100002
#define inf 2000000002
FILE *fin = freopen("zoo.in", "r", stdin);
FILE *fout = freopen("zoo.out", "w", stdout);

using namespace std;
int N, M, sol;
struct event
{
    int x, y;
    bool operator < (const event &other) const
    {
        if(x == other.x)
            return y < other.y;
        return x < other.x;
    }
} E[NMAX];
vector <int> cx;

struct Node
{
    Node* left;
    Node* right;
    int size;
    vector <int> v;
};
Node* emptyNode = new Node();
Node* root;

Node* build(int begin = 0, int end = N)
{
    Node* root = new Node();
    root->size = end - begin;
    if (root->size == 1)
    {
        root->left = emptyNode;
        root->right = emptyNode;
        root->v.push_back(E[begin].y);
    }
    else
    {
        root->left = build(begin, begin + root->size / 2);
        root->right = build(begin + root->size / 2, end);
        root->v.resize(root->left->v.size() + root->right->v.size());
        merge(root->left->v.begin(), root->left->v.end(),
              root->right->v.begin(), root->right->v.end(),
              root->v.begin());
    }
    return root;
}

void query(Node* root, int left, int right, int y1, int y2)
{
    if(root->size == right - left)
    {
        int l = lower_bound(root->v.begin(), root->v.end(), y1) - root->v.begin();
        int r = upper_bound(root->v.begin(), root->v.end(), y2) - root->v.begin();
        sol += r - l;
    }
    else if(right <= root->left->size)
        query(root->left, left, right, y1, y2);
    else if(left >= root->left->size)
        query(root->right, left - root->left->size, right - root->left->size, y1, y2);
    else
    {
        query(root->left, left, root->left->size, y1, y2);
        query(root->right, 0, right - root->left->size, y1, y2);
    }
}

void animals()
{
    scanf("%d", &N);
    for(int i = 0; i < N; ++ i)
        scanf("%d %d", &E[i].x, &E[i].y), cx.push_back(E[i].x);
    sort(E, E + N);
    sort(cx.begin(), cx.end());
    root = build();
}

void zoo()
{
    int x1, y1, x2, y2;
    scanf("%d", &M);
    for(int i = 0; i < M; ++ i)
    {
        scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
        sol = 0;
        int left  = lower_bound(cx.begin(), cx.end(), x1) - cx.begin();
        int right = upper_bound(cx.begin(), cx.end(), x2) - cx.begin();
        query(root, left, right, y1, y2);
        printf("%d\n", sol);
    }

}
int main()
{
    emptyNode->left = emptyNode->right = emptyNode;
    emptyNode->size = 0;
    animals();
    zoo();
    return 0;
}