Cod sursa(job #2095190)

Utilizator refugiatBoni Daniel Stefan refugiat Data 27 decembrie 2017 09:50:27
Problema Ograzi Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 kb
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#define mkp make_pair
#define x first
#define y second.first
#define z second.second
#define AIBS 2000005
using namespace std;
FILE*si=fopen("ograzi.in","r");
FILE*so=fopen("ograzi.out","w");
int n,m,w,h;
vector<pair<int,pair<int,int> > >v;
int aib[AIBS];
void update(int k,int val)
{
    while(k<AIBS)
    {
        //cout<<k<<'\n';
        aib[k]+=val;
        k+=(k&(k^(k-1)));
    }
}
int query(int k)
{
    int sum=0;
    while(k)
    {
        sum+=aib[k];
        k-=(k&(k^(k-1)));
    }
    return sum>0;
}
int main()
{
    int a,b;
    int poz,lg;

    fscanf(si,"%d %d %d %d",&n,&m,&w,&h);
    for(int i=0;i<n;++i)
    {
        fscanf(si,"%d %d",&a,&b);

        ++a;
        ++b;
        //cout<<a<<' '<<b<<'\n';
        v.push_back(mkp(a,mkp(0,b)));
        v.push_back(mkp(a+w,mkp(2,b)));
    }
    for(int i=0;i<m;++i)
    {

        fscanf(si,"%d %d",&a,&b);
        ++a;
        ++b;
        v.push_back(mkp(a,mkp(1,b)));
    }
    int lim=v.size(),rez=0;
    sort(v.begin(),v.end());

    for(int i=0;i<lim;++i)
    {
        //cout<<v[i].z<<'\n';
        if(v[i].y==0)
        {
            update(v[i].z,1);
            update(v[i].z+h+1,-1);
        }
        else
        if(v[i].y==2)
        {
            update(v[i].z,-1);
            update(v[i].z+h+1,1);
        }
        else
        if(v[i].y==1)
            rez+=query(v[i].z);
    }
    fprintf(so,"%d\n",rez);
    return 0;
}