Cod sursa(job #2408300)

Utilizator xRoALexBirtoiu Alexandru xRoALex Data 17 aprilie 2019 19:44:21
Problema Ograzi Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.01 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#define Nmax 100005
#define Val_max 1000005

using namespace std;

FILE *f=fopen("ograzi.in","r");
FILE *g=fopen("ograzi.out","w");

struct element
{
    int x,y,id;
};

int n,m,w,h,ans;
int aib[Val_max+2];
vector <element> drept;
vector <pair<int,int>> oi;

inline bool cmp(element a,element b)
{
    if(a.y==b.y)
        return a.id<b.id;
    return a.y<b.y;
}

inline bool cmp2(pair<int,int> a, pair<int,int> b)
{
    return a.second<b.second;
}

void adauga(int x)
{
    while(x<=Nmax)
    {
        aib[x]++;
        x += (x&(-x));
    }
}

int query(int x)
{
    int s=0;
    while(x)
    {
        s += aib[x];
        x-=(x&(-x));
    }
    return s;
}



int main()
{
    fscanf(f,"%d%d%d%d",&n,&m,&w,&h);
    for(int i=1;i<=n;i++)
    {
        int x,y;
        fscanf(f,"%d%d",&x,&y);
        x++;
        drept.push_back({x,y,0});
        drept.push_back({x,y+h,1});
    }
    sort(drept.begin(),drept.end(),cmp);
    for(int i=1;i<=m;i++)
    {
        int x,y;
        fscanf(f,"%d%d",&x,&y);
        x++;
        oi.push_back({x,y});
    }
    sort(oi.begin(),oi.end(),cmp2);
    /*for(int i=0;i<drept.size();i++)
    {
        fprintf(g,"%d %d %d\n",drept[i].x,drept[i].y,drept[i].id);

    }
    fprintf(g,"\n\n");
    for(int i=0;i<oi.size();i++)
    {
        fprintf(g,"%d %d\n",oi[i].first,oi[i].second);

    }
    fprintf(g,"\n");*/
    int k=0;
    for(int i=0;i<drept.size();i++)
    {

        while(oi[k].second<drept[i].y)
        {
            adauga(oi[k].first);
            k++;
        }
        if(drept[i].id==1)
        {
            while(oi[k].second<=drept[i].y)
        {
            adauga(oi[k].first);
            k++;
        }
        }
        if(drept[i].id ==0)
            ans -= query(drept[i].x+w) - query(drept[i].x);
        else
            ans += query(drept[i].x+w) - query(drept[i].x);
    }
    fprintf(g,"%d",ans);
    return 0;
}