Pagini recente » Autentificare | Cod sursa (job #959971) | Cod sursa (job #668943) | Cod sursa (job #817170) | Cod sursa (job #984327)
Cod sursa(job #984327)
#include <fstream>
#include <algorithm>
#define MAXCORD 1000005
#define MAXS 25
#define MAXN 50005
#define MAXM 100005
using namespace std;
ifstream f("ograzi.in");
ofstream g("ograzi.out");
struct event{
bool tip;
int x,y;};
int n,m,w,h,cnt,sol,cord,nrev,xx,yy;
bool ai[4*MAXCORD];
char s[25];
event ev[MAXN+MAXM];
bool Comp(event a,event b){
if(a.x==b.x)
return a.tip<b.tip;
return a.x<b.x;}
int getnr();
void query(int nod,int st,int dr);
void update(int nod,int st,int dr);
int main()
{
int i;
f>>n>>m>>w>>h;
f.getline(s,MAXS,'\n');
for(i=1;i<=n;i++){
f.getline(s,MAXS,'\n');
cnt=0;
ev[++nrev].x=ev[nrev+1].x=getnr();
ev[nrev].y=ev[nrev+1].y=getnr();
ev[++nrev].x+=w+1;}
for(i=1;i<=m;i++){
f.getline(s,MAXS,'\n');
cnt=0;
ev[++nrev].x=getnr();
ev[nrev].y=getnr();
ev[nrev].tip=1;}
n=nrev;
sort(ev+1,ev+n+1,Comp);
cord=MAXCORD-2;
for(i=1;i<=n;i++){
xx=ev[i].y;
if(ev[i].tip)
query(1,1,cord);
else{
yy=xx+h;
update(1,1,cord);}}
g<<sol<<'\n';
f.close();
g.close();
return 0;
}
int getnr(){
int a=0;
while(s[cnt]>='0'&&s[cnt]<='9')
a=a*10+s[cnt++]-'0';
cnt++;
return a+1;}
void query(int nod,int st,int dr){
if(ai[nod]){
sol++;
return;}
if(st==dr)
return;
int mij=(st+dr)/2;
if(xx<=mij)
return query(2*nod,st,mij);
else
return query(2*nod+1,mij+1,dr);}
void update(int nod,int st,int dr){
if(st>=xx&&dr<=yy){
ai[nod]=1-ai[nod];
return;}
int mij=(st+dr)/2;
if(xx<=mij)
update(2*nod,st,mij);
if(yy>mij)
update(2*nod+1,mij+1,dr);}