Cod sursa(job #2040696)

Utilizator Mihai_PredaPreda Mihai Dragos Mihai_Preda Data 16 octombrie 2017 11:04:46
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.78 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

struct Punct
{
    Punct(int x = 0, int y = 0)
    {
        this->x = x;
        this->y = y;
    }
    int x, y;
};

struct Nod
{
    vector<int> v;
};

const int nMax = 16005;
const int qMax = 100005;
const int valMax = nMax;

int n, m;
vector<Punct> v;
vector<Nod> arb;
int arbSize;

bool cmp_y(const Punct &a, const Punct &b)
{
    return a.y < b.y;
}

bool cmp_y_and_x(const Punct &a, const Punct &b)
{
    if(a.y == b.y)
        return a.x < b.x;
    return a.y < b.y;
}

bool equal_y(const Punct &a, const Punct &b)
{
    return a.y == b.y;
}

void Build(int ind, int st, int dr)
{
    if(st == dr)
    {
        arb[ind].v.push_back(v[st].x);
        return;
    }
    int mid = (st + dr) / 2;
    int fiuSt = 2 * ind;
    int fiuDr = 2 * ind + 1;
    Build(fiuSt, st, mid);
    Build(fiuDr, mid+1, dr);

    if(fiuDr < 2*arbSize)
    {
        arb[ind].v.resize(arb[fiuSt].v.size() + arb[fiuDr].v.size());
        merge(arb[fiuSt].v.begin(), arb[fiuSt].v.end(),
              arb[fiuDr].v.begin(), arb[fiuDr].v.end(),
              arb[ind].v.begin());
    }
    else
        arb[ind].v = arb[fiuSt].v;
}

void preprocess()
{
    sort(v.begin(), v.end(), cmp_y_and_x);
    arbSize = (1 << (int)(ceil(log2(v.size())))) + 1;
    arb.resize(1 << 15);
    Build(1, 0, v.size() - 1);
}

//cate valori din intervalul st...dr sunt intre mn si mx:
int ArbQuery(int st, int dr, int mn, int mx, int currentSt, int currentDr, int nod = 1)
{
    if(st <= currentSt && dr >= currentDr)
        return upper_bound(arb[nod].v.begin(), arb[nod].v.end(), mx) - lower_bound(arb[nod].v.begin(), arb[nod].v.end(), mn);
    int ret = 0;
    int mid = (currentSt + currentDr) / 2;
    if(st <= mid)
        ret += ArbQuery(st, dr, mn, mx, currentSt, mid, 2 * nod);
    if(dr > mid)
        ret += ArbQuery(st, dr, mn, mx, mid + 1, currentDr, 2 * nod + 1);
    return ret;
}

int Query(int minX, int minY, int maxX, int maxY)
{
    minY = lower_bound(v.begin(), v.end(), Punct(0, minY), cmp_y) - v.begin();
    if(minY > n)
        return 0;
    maxY = upper_bound(v.begin(), v.end(), Punct(0, maxY), cmp_y) - v.begin() - 1;
    if(maxY < minY)
        return 0;
    return ArbQuery(minY, maxY, minX, maxX, 0, v.size() - 1);
}

int main()
{
    ifstream in("zoo.in");
    ofstream out("zoo.out");
    in >> n;
    v.resize(n);
    for(int i = 0; i < n; ++i)
        in >> v[i].x >> v[i].y;
    preprocess();
    in >> m;
    int x1, y1, x2, y2;
    for(int i = 1; i <= m; ++i)
    {
        in >> x1 >> y1 >> x2 >> y2;
        out << Query(x1, y1, x2, y2) << "\n";
    }
    in.close();
    out.close();
    return 0;
}