Cod sursa(job #2408314)

Utilizator xRoALexBirtoiu Alexandru xRoALex Data 17 aprilie 2019 20:06:02
Problema Ograzi Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.66 kb
#include <cstdio>
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
#define Nmax 100005
#define Val_max 1000005

using namespace std;

ifstream f("ograzi.in");
ofstream g("ograzi.out");

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;
}

string s;
int p;

/*istream& operator >> (istream& in, int& x){
    while(p < s.size() && s[p] == ' ')
        p++;
    while(p >= s.size()){
        in >> s;
        p = 0;
    }

    x = 0;
    while(p < s.size() && s[p] >= '0' && s[p] <= '9'){
        x = x * 10 + s[p] - '0';
        p++;
    }

    return in;
}
*/
int getx()
{
    while(p < s.size() && s[p] == ' ')
        p++;
    while(p >= s.size()){
        f >> s;
        p = 0;
    }

    int nr=0;
    while(p < s.size() && s[p] >= '0' && s[p] <= '9'){
        nr = nr * 10 + s[p] - '0';
        p++;
    }

    return nr;
}
int main()
{
    n = getx();
    m=getx();
    w=getx();
    h=getx();
    for(int i=1;i<=n;i++)
    {
        int x,y;
        x=getx();
        y=getx();
        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;
        x=getx();
        y=getx();
        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);
    }
    g<<ans;
    return 0;
}