Cod sursa(job #1947296)

Utilizator KusikaPasa Corneliu Kusika Data 30 martie 2017 21:31:24
Problema Zoo Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.85 kb
#include <bits/stdc++.h>
using namespace std;

const int N = 20000;

#define pb push_back
#define X first
#define Y second
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
typedef pair <int,int> PII;

int n, q;
vector <short> t[N];
vector <int> orderx, order[N];
PII P[N];

short gety(int x, int y) {
    short res = 0;
    int v = upper_bound(order[x].begin(),order[x].end(),y-1) - order[x].begin();
    if (v < order[x].size() && order[x][v] == y) v++;
    for (y = v; y; y -= (y & -y)) res += t[x][y-1];
    return res;
}
short get(int x, int y) {
    short res = 0;
    int v = lower_bound(orderx.begin(),orderx.end(),x) - orderx.begin();
    if (v < orderx.size() && orderx[v] == x) v++;
    for (x = v; x; x -= (x & -x)) res += gety(x,y);
    return res;
}

short update(int x, int y) {
    for (;x <= n; x += (x & -x)) {
        int v = upper_bound(order[x].begin(),order[x].end(),y-1) - order[x].begin();
        if (v < order[x].size() && order[x][v] == y) v++;
        for (;v <= order[x].size(); v += (v & -v)) t[x][v-1]++;
    }
}

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

	cin >> n;
	rep(i,0,n) scanf("%d %d", &P[i].X, &P[i].Y);
	sort(P,P+n);
	int id = 0;
	rep(i,0,n) {
	    if (orderx.empty() || orderx.back() != P[i].X) orderx.pb(P[i].X), P[i].X = ++id;
	    else P[i].X = id;
	}
	sort(P,P+n,[&] (PII a, PII b) { return a.Y < b.Y; });
	rep(i,0,n) {
        for (int x = P[i].X; x <= n; x += (x & -x)) {
            order[x].pb(P[i].Y);
            t[x].pb(0);
        }
	}
	rep(i,0,n) update(P[i].X,P[i].Y);

	cin >> q;
	while (q--) {
        int x1, y1, x2, y2;
        scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
        printf("%d\n",get(x2,y2) - get(x2,y1-1) - get(x1-1,y2) + get(x1-1,y1-1));
	}
}