Pagini recente » Cod sursa (job #1277176) | Cod sursa (job #1107328) | Cod sursa (job #1353200) | Cod sursa (job #2474428) | Cod sursa (job #26832)
Cod sursa(job #26832)
#include <cstdio>
#include <algorithm>
#include <string.h>
using namespace std;
#define Nmax 50005
#define Mmax 100005
#define x first
#define tip second.first
#define y second.second
#define mp make_pair
const int Ymax = 1000005;
int n, m, w, h, ct, vl, sol;
pair<int, pair<int, int> > ev[2 * Nmax + Mmax];
char aib[Ymax];
char s[32];
void citire()
{
int i, a, b, ind, l;
scanf("%d %d %d %d\n", &n, &m, &w, &h);
for (i = 1; i <= n; ++i)
{
gets(s);
ind = a = b = 0;
l = strlen(s);
while (s[ind] <= '9' && s[ind] >= '0')
{
a = a * 10 + s[ind] - '0';
++ind;
}
while (!(s[ind] <= '9' && s[ind] >= '0'))
++ind;
while (ind < l && '0' <= s[ind] && s[ind] <= '9')
{
b = b * 10 + s[ind] - '0';
++ind;
}
++a; ++b;
ev[++ct] = mp(a, mp(1, b));
ev[++ct] = mp(a + w, mp(3, b));
}
for (i = 1; i <= m; ++i)
{
gets(s);
ind = a = b = 0;
l = strlen(s);
while (s[ind] <= '9' && s[ind] >= '0')
{
a = a * 10 + s[ind] - '0';
++ind;
}
while (!(s[ind] <= '9' && s[ind] >= '0'))
++ind;
while (ind < l && '0' <= s[ind] && s[ind] <= '9')
{
b = b * 10 + s[ind] - '0';
++ind;
}
++a; ++b;
ev[++ct] = mp(a, mp(2, b));
}
}
void update(int pos)
{
while (pos < Ymax)
{
aib[pos] += vl;
pos += (pos ^ (pos - 1)) & pos;
}
}
int query(int pos)
{
int ret = 0;
while (pos > 0)
{
ret += aib[pos];
pos -= (pos ^ (pos - 1)) & pos;
}
return ret;
}
void solve()
{
int i;
sort(ev + 1, ev + ct + 1);
for (i = 1; i <= ct; ++i)
{
if (ev[i].tip == 1)
{
vl = 1;
update(ev[i].y);
vl = -1;
update(ev[i].y + h + 1);
}
else if (ev[i].tip == 3)
{
vl = -1;
update(ev[i].y);
vl = 1;
update(ev[i].y + h + 1);
}
else if (ev[i].tip == 2)
{
if (query(ev[i].y) > 0)
++sol;
}
}
printf("%d\n", sol);
}
int main()
{
freopen("ograzi.in", "r", stdin);
freopen("ograzi.out", "w", stdout);
citire();
solve();
return 0;
}