Cod sursa(job #2335732)

Utilizator patcasrarespatcas rares danut patcasrares Data 4 februarie 2019 14:39:45
Problema Ograzi Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.13 kb
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
ofstream fout("ograzi.out");
const int DN=5e5+5,DM=1e6+5;
int n,m,w,h,f,g,nr,type,val,rez;
int aib[DM];
pair<int,pair<int,int> >a[DN],lst2[DN];
FILE* fin=fopen("ograzi.in","r");
const unsigned maxb=30192;
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]={(2e6-l+1)*10+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];
		if(sum>0)
            return 1;
		poz-=(poz&(-poz));
	}
	return sum;
}
int fr[10005];
void sortare(int n)
{
    int p=1;
    int DM=10005;
    for(int h=1;h<3;h++)
    {
        for(int i=0;i<DM;i++)
            fr[i]=0;
        for(int i=1;i<=n;i++)
        {
            lst2[i]=a[i];
            //cout<<a[i].x.x<<'\n';
            fr[(a[i].x/p)%10000]++;
        }
        for(int i=1;i<DM;i++)
            fr[i]+=fr[i-1];
        for(int i=DM-1;i>0;i--)
            fr[i]=fr[i-1];
        fr[0]=0;
        for(int i=1;i<=n;i++)
        {
            fr[(lst2[i].x/p)%10000]++;
            a[fr[(lst2[i].x/p)%10000]]=lst2[i];
        }
        p*=10000;
    }
}
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);
	}
	sortare(nr);
	for(int h=1;h<=nr;h++)
	{
		type=a[h].x%10;
		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;
}