Pagini recente » Cod sursa (job #958804) | Cod sursa (job #2355340) | Cod sursa (job #500874) | Cod sursa (job #2158306) | Cod sursa (job #28797)
Cod sursa(job #28797)
#include <stdio.h>
#include <algorithm>
#define nmax 1000001
#define omax 100002
#define dmax 50002
using namespace std;
struct point
{
int x, y;
};
int n, m, w, h, aib[nmax], sol;
bool cmp(point one, point two)
{
return one.x < two.x || (one.x == two.x && one.y <= two.y);
}
void add(int val, int pos);
int query(int pos);
int main()
{
freopen("ograzi.in","r",stdin);
freopen("ograzi.out","w",stdout);
scanf("%d%d%d%d ", &n, &m, &w, &h);
point o[omax], d[dmax];
int i, j, first = 1, last = 0;
char line [32];
for(i = 1; i <= n; ++i)
{
j = d[i].x = d[i].y = 0;
fgets(line, 32, stdin);
for(j = 0; '0' <= line[j] && line[j] <= '9'; ++j)
{
d[i].x *= 10;
d[i].x += line[j] - '0';
}
for(++j; '0' <= line[j] && line[j] <= '9'; ++j)
{
d[i].y *= 10;
d[i].y += line[j] - '0';
}
// scanf("%d%d", &d[i].x, &d[i].y);
}
sort(d + 1, d + n + 1, cmp);
for(i = 1; i <= m; ++i)
{
j = o[i].x = o[i].y = 0;
fgets(line, 32, stdin);
for(j = 0; '0' <= line[j] && line[j] <= '9'; ++j)
{
o[i].x *= 10;
o[i].x += line[j] - '0';
}
for(++j; '0' <= line[j] && line[j] <= '9'; ++j)
{
o[i].y *= 10;
o[i].y += line[j] - '0';
}
}
sort(o + 1, o + m + 1, cmp);
for(i = 1; i <= m; ++i)
{
while(o[i].x >= d[last + 1].x && last < n)
{
++last;
add(1, d[last].y);
}
while(o[i].x > d[first].x + w && first <= last)
{
add(-1, d[first].y);
++first;
}
if(o[i].y - h - 1 < 0)
sol += query(o[i].y);
else
sol += query(o[i].y) - query(o[i].y - h - 1);
}
printf("%d", sol);
return 0;
}
void add(int val, int pos)
{
while(pos < nmax)
{
aib[pos] += val;
pos += pos & (pos ^ (pos - 1));
// pos += ~(pos-1)&pos;
}
}
int query(int pos)
{
int rez = 0;
while(pos)
{
rez += aib[pos];
pos -= pos & (pos ^ (pos - 1));
// pos -= ~(pos-1)&pos;
}
return rez;
}