Pagini recente » Cod sursa (job #57946) | Cod sursa (job #2785180) | Cod sursa (job #698139) | Cod sursa (job #1461172) | Cod sursa (job #2440630)
#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#define fi first
#define se second
#define pb push_back
using namespace std;
ifstream f("zoo.in");
ofstream g("zoo.out");
typedef long long ll;
int n, q;
pair<int, int> v[16002];
struct rct
{
int xa, ya;
int xb, yb;
int ans;
};
rct qu[102002];
short mat[5002][5002];
set<int>sx, sy;
int vx[5002], vy[5002];
int L, C;
int cbx(int val)
{
int st = 1;
int dr = L;
int ans = 0;
while(st <= dr)
{
int mid = (st + dr) / 2;
if(vx[mid] <= val)
ans = mid, st = mid + 1;
else
dr = mid - 1;
}
return ans;
}
int cby(int val)
{
int st = 1;
int dr = C;
int ans = 0;
while(st <= dr)
{
int mid = (st + dr) / 2;
if(vy[mid] <= val)
ans = mid, st = mid + 1;
else
dr = mid - 1;
}
return ans;
}
int sum(int xa, int ya, int xb, int yb)
{
return mat[xb][yb] - (xa > 0) * mat[xa-1][yb] - (ya > 0) * mat[xb][ya-1] + (xa > 0 && ya > 0) * mat[xa-1][ya-1];
}
void solve(int st, int dr)
{
sx.clear();
sy.clear();
for(int i = st; i <= dr; ++i)
sx.insert(v[i].fi), sy.insert(v[i].se);
set<int> ::iterator it;
L = 0, C = 0;
for(it = sx.begin(); it != sx.end(); ++it)
vx[++L] = *it;
for(it = sy.begin(); it != sy.end(); ++it)
vy[++C] = *it;
for(int i = st; i <= dr; ++i)
{
pair<int, int> poz;
poz.fi = cbx(v[i].fi);
poz.se = cby(v[i].se);
mat[poz.fi][poz.se]++;
}
for(int i = 1; i <= L; ++i)
for(int j = 1; j <= C; ++j)
mat[i][j] = mat[i][j] + mat[i-1][j] + mat[i][j-1] - mat[i-1][j-1];
for(int i = 1; i <= q; ++i)
{
int aa = cbx(qu[i].xa);
int bb = cby(qu[i].ya);
int cc = cbx(qu[i].xb);
int dd = cby(qu[i].yb);
qu[i].ans = qu[i].ans + sum(aa, bb, cc, dd);
}
for(int i = st; i <= dr; ++i)
{
pair<int, int> poz;
poz.fi = cbx(v[i].fi);
poz.se = cby(v[i].se);
mat[poz.fi][poz.se]--;
}
}
int main()
{
f >> n;
for(int i = 1; i <= n; ++i)
f >> v[i].fi >> v[i].se;
f >> q;
for(int i = 1; i <= q; ++i)
f >> qu[i].xa >> qu[i].ya >> qu[i].xb >> qu[i].yb;
int lst = 0;
for(int i = 1; i <= n; ++i)
if(i % 5000 == 0 || i == n)
solve(lst+1, i), lst = i;
for(int i = 1; i <= q; ++i)
g << qu[i].ans << '\n';
return 0;
}