Cod sursa(job #170102)

Utilizator ScrazyRobert Szasz Scrazy Data 2 aprilie 2008 13:26:36
Problema Ograzi Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

#define pb push_back
#define mp make_pair
#define all(c) (c).begin(), (c).end()
#define tip second.first
#define x first
#define y second.second
int n, m, w, h; 

const int MAX_C = 1000010;

int T[MAX_C];
typedef pair<int,int> PII;
vector<pair<int,PII> > E;
int sol = 0;

void update(int idx, int val)
{
    while (idx < MAX_C)
    {
	T[idx] += val;
	idx += (idx & -idx);
    }
}

int query(int idx)
{
    int sum = 0;
    while (idx > 0)
    {
	sum += T[idx];
	idx -= (idx & -idx);
    }
    return sum;
}

int main()
{
    freopen("ograzi.in","r",stdin);
    freopen("ograzi.out","w",stdout);

    scanf("%d%d%d%d", &n, &m, &w, &h);
    for (int i = 0; i < n; ++i)
    {
	int xx, yy;
	scanf("%d%d", &xx, &yy);
	E.pb(mp(xx,mp(1,yy)));E.pb(mp(xx + w,mp(2,yy)));
    }
    for (int i = 0; i < m; ++i)
    {
	int xx, yy;
	scanf("%d%d", &xx, &yy);
	E.pb(mp(xx,mp(3,yy)));
    }

    sort(all(E));

    for (int i = 0; i < (int)E.size(); ++i)
    {
	if (E[i].tip == 1)
	{
	   update(E[i].y,1);
	   update(E[i].y + h + 1,-1);
	}
	else if (E[i].tip == 2)
	{
	   update(E[i].y,-1);
	   update(E[i].y + h + 1,1);
	}
	else if (E[i].tip == 3)
	{
	    if (query(E[i].y) > 0) ++sol;
	}
    }
    printf("%d\n", sol);

    return 0;
}