Pagini recente » Cod sursa (job #2480656) | Cod sursa (job #3193643)
#include <bits/stdc++.h>
#define lsb(x) ((x ^ (x - 1)) & x)
using namespace std;
ifstream fin ("ograzi.in");
ofstream fout ("ograzi.out");
int n, m, H, W;
int srt[300040];
struct puncte{
int x, y;
};
puncte v[100010], p[50010];
int aib[200020];
void update_aib(int pos, int val){
for(;pos <= n; pos += lsb(pos))
aib[pos] += val;
return ;
}
int query(int pos){
int sum = 0;
for(;pos > 0; pos -= lsb(pos))
sum = sum + aib[pos];
return sum;
}
bool cmp(puncte a, puncte b){
return a.x < b.x;
}
int main()
{
fin >> n >> m >> W >> H;
int k = 0;
for(int i = 1; i <= n; ++i){
fin >> v[i].x >> v[i].y;
srt[++k] = v[i].x;
srt[++k] = v[i].y;
}
for(int i = 1; i <= m; ++i){
fin >> p[i].x >> p[i].y;
srt[++k] = p[i].x;
srt[++k] = p[i].y;
}
sort(srt + 1, srt + k + 1);
///int L = unique(srt + 1, srt + k + 1) - srt - 1;
for(int i = 1; i <= n; ++i)
{
v[i].x = lower_bound(srt + 1, srt + k + 1, v[i].x) - srt;
v[i].y = lower_bound(srt + 1, srt + k + 1, v[i].y) - srt;
}
for(int i = 1; i <= m; ++i)
{
p[i].x = lower_bound(srt + 1, srt + k + 1, p[i].x) - srt;
p[i].y = lower_bound(srt + 1, srt + k + 1, p[i].y) - srt;
}
sort(v + 1, v + n + 1, cmp);
sort(p + 1, p + n + 1, cmp);
int pos = 1, poz = 1, pos_ant = 1;
int i = 1, ans = 0;
while(pos <= n && poz <= m)
{
///cout << query(100) << "\n";
while(v[pos_ant].x + W < i && pos_ant <= n)
{
update_aib(v[pos_ant].y, -1);
update_aib(v[pos_ant].y + H + 1, 1);
++pos_ant;
}
while(v[pos].x <= i && pos <= n)
{
update_aib(v[pos].y, 1);
update_aib(v[pos].y + H + 1, -1);
++pos;
}
while(p[poz].x <= i && poz <= m)
{
ans = ans + query(p[poz].y);
cout << query(p[poz].y) << "\n";
++poz;
}
++i;
}
while(pos_ant <= n && poz <= m)
{
///cout << query(100) << "\n";
while(v[pos_ant].x + W < i && pos_ant <= n)
{
update_aib(v[pos_ant].y, -1);
update_aib(v[pos_ant].y + H + 1, 1);
++pos_ant;
}
while(p[poz].x <= i && poz <= m)
{
ans = ans + query(p[poz].y);
cout << query(p[poz].y) << "\n";
++poz;
}
++i;
}
fout << ans;
return 0;
}