Cod sursa(job #1277353)

Utilizator assa98Andrei Stanciu assa98 Data 27 noiembrie 2014 16:19:13
Problema Zoo Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.5 kb
#include <fstream>
#include <vector>
#include <algorithm>

#define pe pair<int, int>
#define se second
#define fi first
#define mp make_pair

using namespace std;

ifstream fin("zoo.in");
ofstream fout("zoo.out");

const int MAX_N = 16100;

class TR {
private:
    int sum;
    int ver;
    TR *f1, *f2;
public:
    TR(int _sum = 0, int _ver = 0) {
        sum = _sum;
        ver = 0;
        f1 = f2 = NULL;
    }

    void build(int st, int dr) {
        if(st == dr) {
            return;
        }

        int mij = (st + dr) / 2;
        f1 = new TR();
        f2 = new TR();
        f1->ver = ver;
        f2->ver = ver;
        f1->build(st, mij);
        f2->build(mij + 1, dr);
    }

    int query(int st, int dr, int a, int b) {
        if(st >= a && dr <= b) {
            return sum;
        }

        int mij = (st + dr) / 2;
        int ans = 0;
        if(a <= mij) {
            ans += f1->query(st, mij, a, b);
        }
        if(b > mij) {
            ans += f2->query(mij + 1, dr, a, b);
        }
        return ans;
    }

    void update(TR *ant, int st, int dr, int poz) {
        if(st == dr) {
            sum++;
            return;
        }

        int mij = (st + dr) / 2;
        if(poz <= mij) {
            if(f1 == NULL) {
                f1 = new TR(ant->f1->sum, ver);
                f2 = ant->f2;
            }
            else if(f1->ver != ver) {
                f1 = new TR(ant->f1->sum, ver);
            }
            f1->update(ant->f1, st, mij, poz);
        }
        else {
            if(f2 == NULL) {
                f2 = new TR(ant->f2->sum, ver);
                f1 = ant->f1;
            }
            else if(f2->ver != ver) {
                f2 = new TR(ant->f2->sum, ver);
            }
            f2->update(ant->f2, mij + 1, dr, poz);
        }
        sum = f1->sum + f2->sum;
    }
};

TR *R[MAX_N];

vector<pe> v;
vector<int> normY;
vector<int> normX;

int main() {
    int n;
    fin >> n;
    for(int i = 1; i <= n; i++) {
        int x, y;
        fin >> x >> y;
        v.push_back(mp(x, y));
        normY.push_back(y);
        normX.push_back(x);
    }

    sort(v.begin(), v.end());
    sort(normX.begin(), normX.end());
    sort(normY.begin(), normY.end());
    normX.erase(unique(normX.begin(), normX.end()), normX.end());
    normY.erase(unique(normY.begin(), normY.end()), normY.end());

    int p;
    for(p = 1; p < (int)normY.size(); p *= 2);

    R[0] = new TR();
    R[0]->build(1, p);

    for(auto it : v) {
        int x = lower_bound(normX.begin(), normX.end(), it.fi) - normX.begin();
        int y = lower_bound(normY.begin(), normY.end(), it.se) - normY.begin() + 1; //1 .. normY.size()
        if(R[x] == NULL) {
            R[x] = new TR(0, x);
        }
        if(x == 0) {
            R[x]->update(R[x], 1, p, y);
        }
        else {
            R[x]->update(R[x - 1], 1, p, y);
        }
    }

    int m;
    fin >> m;
    for(int i = 1; i <= m; i++) {
        int x1, y1, x2, y2;
        fin >> x1 >> y1 >> x2 >> y2;
        y1 = lower_bound(normY.begin(), normY.end(), y1) - normY.begin() + 1;
        y2 = lower_bound(normY.begin(), normY.end(), y2) - normY.begin() + 1;
        x1 = upper_bound(normX.begin(), normX.end(), x1 - 1) - normX.begin() - 1;
        x2 = upper_bound(normX.begin(), normX.end(), x2) - normX.begin() - 1;

        int ans = 0;
        if(x2 != -1) {
            ans += R[x2]->query(1, p, y1, y2);
            if(x1 != -1) {
                ans -= R[x1]->query(1, p, y1, y2);
            }
        }

        fout << ans << '\n';
    }
    return 0;
}