Cod sursa(job #2335669)

Utilizator patcasrarespatcas rares danut patcasrares Data 4 februarie 2019 13:47:02
Problema Ograzi Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.22 kb
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
ofstream fout("ograzi.out");
const int DN=5e5+5,DM=2e6+5;
int n,m,w,h,f,g,nr,type,val,rez;
int aib[DM];
pair<pair<int,int>,pair<int,int> >a[DN];
ifstream fin("ograzi.in");
const unsigned maxb=30192;
char buf[maxb];
unsigned ptr=maxb-1;
inline int getint()
{
    int nr;
    fin>>nr;
    return nr;
}
void add(int l,int type,int c,int val)
{
	nr++;
	a[nr]={{-l,type},{c,val}};
}
void update(int poz,int val)
{
	while(poz<DM)
	{
		aib[poz]+=val;
		poz+=(poz&(-poz));
	}
}
int suma(int poz)
{
	int sum=0;
	while(poz>0)
	{
		sum+=aib[poz];
		poz-=(poz&(-poz));
	}
	return sum;
}
int main()
{
	n=getint();
	m=getint();
	w=getint();
	h=getint();
	for(int i=1;i<=n;i++)
	{
		f=getint();
		g=getint();
		f++;
		//cout<<'z'<<g-h<<'\n';
		add(g+h,0,f,1);
		add(g+h,0,f+w+1,-1);
		add(g-1,0,f,-1);
		add(g-1,0,f+w+1,1);
	}
	for(int i=1;i<=m;i++)
	{
		f=getint();
		g=getint();
		f++;
		add(g,1,f,0);
	}
	sort(a+1,a+nr+1);
	for(int h=1;h<=nr;h++)
	{
		type=a[h].x.y;
		if(type==0)
		{
			update(a[h].y.x,a[h].y.y);
			continue;
		}
		val=suma(a[h].y.x);
		if(val>0)
			val=1;
		rez+=val;
	}
	fout<<rez;
}