Cod sursa(job #2335661)

Utilizator patcasrarespatcas rares danut patcasrares Data 4 februarie 2019 13:41:47
Problema Ograzi Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.49 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];
FILE* fin=fopen("ograzi.in","r");
const unsigned maxb=30000192;
char buf[maxb];
unsigned ptr=maxb-1;
inline unsigned getint()
{
    unsigned nr=0;
    while(buf[ptr]<'0'||buf[ptr]>'9')
        if(++ptr>=maxb)
            fread(buf,maxb,1,fin),ptr=0;
    while(buf[ptr]>='0'&&buf[ptr]<='9')
    {
        nr=nr*10+buf[ptr]-'0';
        if(++ptr>=maxb)
            fread(buf,maxb,1,fin),ptr=0;
    }
    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();
		g++;
		//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();
		g++;
		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;
}