Pagini recente » Cod sursa (job #1280985) | Cod sursa (job #127415) | Cod sursa (job #2280941) | Cod sursa (job #655331) | Cod sursa (job #26827)
Cod sursa(job #26827)
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define mp make_pair
#define x first
#define y second.first
#define z second.second
#define pb push_back
#define sz size()
#define lsb(a) (a & (a ^ (a-1)))
#define Rmax 1000005
int n, m, w, h;
vector< pair< int, pair<int, int> > > v;
char aib[Rmax];
void readdata()
{
freopen("ograzi.in", "r", stdin);
freopen("ograzi.out", "w", stdout);
int i, a, b;
char s[16], poz, lung;
scanf("%d %d %d %d\n", &n, &m, &w, &h);
for (i = 0; i < n; ++i)
{
gets(s);
lung = strlen(s);
a = b = 0;
poz = 0;
while (s[poz] >= '0' && s[poz] <= '9')
a = a*10 + s[poz++]- '0';
while (!(s[poz] >= '0' && s[poz] <= '9'))
++poz;
while (poz < lung && s[poz] >= '0' && s[poz] <= '9')
b = b*10 + s[poz++]-'0';
++a, ++b;
v.pb( mp(a, mp(0, b)) );
v.pb( mp(a+w, mp(2, b)) );
}
for (i = 0; i < m; ++i)
{
gets(s);
lung = strlen(s);
a = b = 0;
poz = 0;
while (s[poz] >= '0' && s[poz] <= '9')
a = a*10 + s[poz++]- '0';
while (!(s[poz] >= '0' && s[poz] <= '9'))
++poz;
while (poz < lung && s[poz] >= '0' && s[poz] <= '9')
b = b*10 + s[poz++]-'0';
++a, ++b;
v.pb( mp(a, mp(1, b)) );
}
}
void update(int k, int val)
{
while (k < Rmax)
{
aib[k] += val;
k += lsb(k);
}
}
char query(int k)
{
int sum = 0;
while (k)
{
sum += aib[k];
k -= lsb(k);
}
return sum > 0;
}
void solve()
{
int i, lim = v.sz, rez = 0;
sort(v.begin(), v.end());
for (i = 0; i < lim; ++i)
{
if (v[i].y == 0)
{
update(v[i].z, 1);
update(v[i].z+h+1, -1);
}
if (v[i].y == 2)
{
update(v[i].z, -1);
update(v[i].z+h+1, 1);
}
if (v[i].y == 1)
rez += query(v[i].z);
}
printf("%d\n", rez);
}
int main()
{
readdata();
solve();
return 0;
}