Cod sursa(job #2172834)

Utilizator Alexa2001Alexa Tudose Alexa2001 Data 15 martie 2018 18:14:00
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.2 kb
#include <bits/stdc++.h>

using namespace std;

const int Nmax = 20005, Qmax = 1e5 + 5;

int nr, i, n, Q, X1, X2, Y1, Y2, limx, limy, ans[Qmax];
vector<int> upd[Nmax], allX, allY;
vector< pair<int,int> > que[Nmax];

struct point
{
    int x, y;
} a[Nmax];

class AIB
{
    int a[Nmax];
    int ub(int x) { return (x&(-x)); }

    public:
        int query(int pos)
        {
            int ans = 0;
            for(; pos; pos-=ub(pos)) ans += a[pos];
            return ans;
        }

        void update(int pos)
        {
            for(; pos<=limy; pos+=ub(pos)) a[pos] ++;
        }

} aib;

int bs(vector<int> &v, int val) /// max <=
{
    int st = 0, dr = v.size() - 1, mid;
    while(st <= dr)
    {
        mid = (st+dr)/2;
        if(v[mid] <= val) st = mid+1;
            else dr = mid-1;
    }
    return st;
}

void normalize()
{
    int i;
    for(i=1; i<=n; ++i) allX.push_back(a[i].x), allY.push_back(a[i].y);
    sort(allX.begin(), allX.end());
    sort(allY.begin(), allY.end());
    allX.erase( unique(allX.begin(), allX.end()), allX.end() );
    allY.erase( unique(allY.begin(), allY.end()), allY.end() );

    limx = allX.size(); limy = allY.size();

    for(i=1; i<=n; ++i)
        upd[bs(allX, a[i].x)].push_back(bs(allY, a[i].y));
}

int main()
{
    freopen("zoo.in", "r", stdin);
    freopen("zoo.out", "w", stdout);

    scanf("%d", &n);
    for(i=1; i<=n; ++i)
        scanf("%d %d\n", &a[i].x, &a[i].y);
    normalize();

    scanf("%d", &Q);
    for(i=1; i<=Q; ++i)
    {
        scanf("%d %d %d %d\n", &X1, &Y1, &X2, &Y2);
        X1 = bs(allX, X1-1);
        X2 = bs(allX, X2);

        Y1 = bs(allY, Y1-1);
        Y2 = bs(allY, Y2);

        que[X1].push_back({Y1, i});
        que[X2].push_back({Y2, i});

        que[X1].push_back({Y2, -i});
        que[X2].push_back({Y1, -i});
    }

    for(i=1; i<=limx; ++i)
    {
        for(auto y : upd[i]) aib.update(y);

        for(auto q : que[i])
        {
            nr = aib.query(q.first);
            if(q.second < 0) ans[-q.second] -= nr;
                else ans[q.second] += nr;
        }
    }

    for(i=1; i<=Q; ++i) printf("%d\n", ans[i]);
    return 0;
}