Cod sursa(job #1232720)

Utilizator assa98Andrei Stanciu assa98 Data 23 septembrie 2014 20:05:53
Problema Zoo Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.85 kb
#include <fstream>
#include <algorithm>
#include <vector>

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

using namespace std;

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

struct que {
    int tip;
    int x, y;
    int poz;
    que(int _tip = 0, int _x = 0, int  _y = 0, int  _poz = 0) {
        tip = _tip;
        x = _x;
        y = _y;
        poz = _poz;
    }
    inline bool operator < (const que &a) const {
        if(x == a.x) {
            if(y == a.y) {
                return tip < a.tip;
            }
            return y < a.y;
        }
        return x < a.x;
    }
};

const int MAX_N = 16100;
const int MAX_M = 100100;
const int INF = 2000000000;

vector<int> x;
vector<int> y;

vector<pe> A;
vector<pair<pe, pe> > Q;

vector<que> op;

int sol[MAX_N];
int aib[4 * MAX_M];

void update(int poz, int val) {
    while(poz < 4 * MAX_M) {
        aib[poz] += val;
        poz += (poz & (-poz));
    }
}

int query(int poz) {
    int s = 0;
    while(poz) {
        s += aib[poz];
        poz -= (poz & (-poz));
    }
    return s;
}

int main() {
    int n, m;
    fin >> n;
    for(int i = 1; i <= n; i++) {
        int a, b;
        fin >> a >> b;
        A.push_back(mp(a, b));
        x.push_back(a);
        y.push_back(b);
    }

    fin >> m;
    for(int i = 1; i <= m; i++) {
        int x1, x2, y1, y2;
        fin >> x1 >> y1 >> x2 >> y2;
        x.push_back(x1);
        x.push_back(x2);
        y.push_back(y1);
        y.push_back(y2);
        Q.push_back(mp(mp(x1, y1), mp(x2, y2)));
    }

    x.push_back(-INF - 1);
    y.push_back(-INF - 1);
    sort(x.begin(), x.end());
    sort(y.begin(), y.end());
    x.erase(unique(x.begin(), x.end()), x.end());
    y.erase(unique(y.begin(), y.end()), y.end());

    for(auto it : A) {
        int a = lower_bound(x.begin(), x.end(), it.fi) - x.begin();
        int b = lower_bound(y.begin(), y.end(), it.se) - y.begin();
        op.push_back(que(0, a, b, 0));
    }
    for(auto i = 0; i < (int)Q.size(); i++) {
        auto it = Q[i];
        int x1 = lower_bound(x.begin(), x.end(), it.fi.fi) - x.begin();
        int y1 = lower_bound(y.begin(), y.end(), it.fi.se) - y.begin();
        int x2 = lower_bound(x.begin(), x.end(), it.se.fi) - x.begin();
        int y2 = lower_bound(y.begin(), y.end(), it.se.se) - y.begin();
        op.push_back(que(1,  x1 - 1,  y1 - 1, i + 1));
        op.push_back(que(1,  x2,  y2, i + 1));
        op.push_back(que(2,  x1 - 1,  y2, i + 1));
        op.push_back(que(2,  x2,  y1 - 1, i + 1));
    }

    sort(op.begin(), op.end());
    for(auto it : op) {
        if(it.tip == 0) {
            update(it.y, 1);
        }
        else if(it.tip == 1) {
            sol[it.poz] += query(it.y);
        }
        else {
            sol[it.poz] -= query(it.y);
        }
    }

    for(int i = 1; i <= m; i++) {
        fout << sol[i] << '\n';
    }

    return 0;
}