Pagini recente » Cod sursa (job #837535) | Cod sursa (job #490870) | Cod sursa (job #2282600) | Cod sursa (job #1551418) | Cod sursa (job #852666)
Cod sursa(job #852666)
#include <fstream>
#include <algorithm>
#include <vector>
#define MAX 16005
#define RMAX 100005
#define INF 2000000050
#define PII pair<int, int>
#define f first
#define s second
#define mp make_pair
#define pb push_back
using namespace std;
int N, M, maxim, Y[(RMAX << 1) + MAX], AIB[(RMAX << 1) + MAX], ans[RMAX];
PII V[MAX];
struct PUNCT
{
int X, Y, ind, sign;
}add;
vector<PUNCT> Q;
struct RECT
{
int x1, y1, x2, y2;
} R[RMAX];
void citire()
{
ifstream in("zoo.in"); in>>N;
for(int i = 1; i <= N; i++) in>>V[i].f>>V[i].s;
in>>M; sort(V + 1, V + N + 1);
for(int i = 1; i <= M; i++)
{
in>>R[i].x1>>R[i].y1>>R[i].x2>>R[i].y2;
} in.close();
}
void normalize()
{
int n = 0;
for(int i = 1; i <= N; i++) Y[++n] = V[i].s;
for(int i = 1; i <= M; i++)
{
Y[++n] = R[i].y1;
Y[++n] = R[i].y2;
} sort(Y + 1, Y + n + 1);
Y[0] = -INF; int i, j;
for(i = 1, j = 0; i <= n; i++)
if(Y[i] != Y[j]) Y[++j] = Y[i];
maxim = j;
for(int i = 1; i <= N; i++) V[i].s = lower_bound(Y + 1, Y + j + 1, V[i].s) - Y;
for(int i = 1; i <= M; i++)
{
R[i].y1 = lower_bound(Y + 1, Y + j + 1, R[i].y1) - Y;
R[i].y2 = lower_bound(Y + 1, Y + j + 1, R[i].y2) - Y;
}
}
bool cmp(PUNCT a, PUNCT b)
{
return a.X < b.X;
}
void adauga()
{
for(int i = 1; i <= M; i++)
{
add.X = R[i].x1 - 1, add.Y = R[i].y1 - 1, add.ind = i, add.sign = 1;
Q.pb(add);
add.X = R[i].x2, add.Y = R[i].y2, add.ind = i, add.sign = 1;
Q.pb(add);
add.X = R[i].x2, add.Y = R[i].y1 - 1, add.ind = i, add.sign = -1;
Q.pb(add);
add.X = R[i].x1 - 1, add.Y = R[i].y2, add.ind = i, add.sign = -1;
Q.pb(add);
} sort(Q.begin(), Q.end(), cmp);
}
void update(int Y)
{
for(int i = Y; i <= maxim; i += (i & (-i)))
AIB[i]++;
}
int query(int Y)
{
int rez = 0;
for(int i = Y; i; i -= (i & (-i)))
rez += AIB[i];
return rez;
}
int main()
{
citire();
normalize();
adauga();
for(size_t i = 0, ind = 1; i < Q.size(); i++)
{
for(; V[ind].f <= Q[i].X && ind <= N; ind++)
update(V[ind].s);
ans[Q[i].ind] += Q[i].sign * query(Q[i].Y);
}
ofstream out("zoo.out");
for(int i = 1; i <= M; i++) out<<ans[i]<<"\n";
out.close();
return 0;
}