Pagini recente » Cod sursa (job #1759837) | Cod sursa (job #2031305) | Cod sursa (job #1213644) | Cod sursa (job #194719) | Cod sursa (job #2443096)
#include <bits/stdc++.h>
using namespace std;
ifstream fi("ograzi.in");
ofstream fo("ograzi.out");
#define cin fi
#define cout fo
const int NMAX = 1e6 + 10;
int n, m, w, h;
vector < pair<int, int> > dr, oi;
int aib[NMAX];
inline int lsb(int x)
{
return (x & (-x));
}
void update(int poz, int val)
{
for (int i = poz; i < NMAX; i += lsb(i))
aib[i] += val;
}
int getSum(int poz)
{
int ret = 0;
for (int i = poz; i; i -= lsb(i))
ret += aib[i];
return ret;
}
int query(int st, int dr)
{
if (st == 0)
return getSum(dr);
return getSum(dr) - getSum(st - 1);
}
int main()
{
cin >> n >> m >> w >> h;
for (int i = 1; i <= n; i++)
{
int x, y;
cin >> x >> y;
dr.push_back({y, x});
}
for (int i = 1; i <= m; i++)
{
int x, y;
cin >> x >> y;
oi.push_back({y, x});
}
int rez = 0;
int currDr = 0, currOi = 0, currOi2 = 0;
// liniile 0...h
for (int i = 0; i <= h; i++)
{
while (currOi < oi.size() && oi[currOi].first == i)
{
update(oi[currOi].second, 1);
}
}
while (currDr < dr.size() && dr[currDr].first == 0)
{
pair <int, int> da = dr[currDr];
rez += query(da.second, da.second + w);
currDr++;
}
for (int i = h + 1; i <= 1e6 + 5; i++)
{
// bag linia i, scot linia i-h-1
while (currOi < oi.size() && oi[currOi].first == i)
update(oi[currOi].second, 1), currOi++;
while (currOi2 < oi.size() && oi[currOi2].first == i - h - 1)
update(oi[currOi2].second, -1), currOi2++;
while (currDr < dr.size() && dr[currDr].first == i - h)
{
pair <int, int> da = dr[currDr];
rez += max(0, query(da.second, da.second + w));
currDr++;
}
}
for (int i = 1e6 + 6; i <= 2e6 + 5; i++)
while (currDr < dr.size() && dr[currDr].first == i - h)
{
pair <int, int> da = dr[currDr];
rez += max(0, query(da.second, da.second + w));
currDr++;
}
cout << rez << "\n";
//cout << (sizeof(dr) + sizeof(oi) + sizeof(aib)) / 1000;
return 0;
}