Cod sursa(job #1182232)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 5 mai 2014 11:38:32
Problema Zoo Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.33 kb
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>

using namespace std;

map<int,int> hartax;
map<int,int> hartay;



struct punct
{
    int x;
    int y;
}v[16005];

struct drept
{
    punct a;
    punct b;
    int val;

    drept()
    {
        val=0;
    }
}d[100005];

vector<int> pe_x;
vector<int> pe_y;

#define lsb(x) ((x)&(-x))
int aib[300005];

inline void update(int poz)
{
    for(;poz<=300005;poz+=lsb(poz))
        aib[poz]++;
}

int sum(int poz)
{
    int s=0;
    for(;poz>0;poz-=lsb(poz))
        s+=aib[poz];
    return s;
}

struct elem
{
    int x;
    int y;
    int indice;
    bool tip;
};

bool operator<(const elem &a,const elem &b)
{
    if(a.x<b.x)
        return 1;
    if(a.x>b.x)
        return 0;

    if(a.tip<b.tip)
        return 1;
    return 0;
}

elem make_elem(punct pt,int ind,bool tp)
{
    elem aux;
    aux.tip=tp;
    aux.indice=ind;
    aux.x=pt.x;
    aux.y=pt.y;

    return aux;
}

vector<elem> parc;

int main()
{
    int n,m,i;
    cin>>n;

    for(i=1;i<=n;i++)
    {
        cin>>v[i].x>>v[i].y;
        pe_x.push_back(v[i].x);
        pe_y.push_back(v[i].y);
    }

    cin>>m;
    for(i=1;i<=m;i++)
    {
        cin>>d[i].a.x>>d[i].a.y>>d[i].b.x>>d[i].b.y;
        pe_x.push_back(d[i].a.x-1);
        pe_x.push_back(d[i].b.x);

        pe_y.push_back(d[i].a.y-1);
        pe_y.push_back(d[i].b.y);
    }

    sort(pe_x.begin(),pe_x.end());
    sort(pe_y.begin(),pe_y.end());

    int ante=pe_x[0]-1;
    int curent=0;

    for(i=0;i<pe_x.size();i++)
    {
        if(pe_x[i]!=ante)
        {
            ante=pe_x[i];
            curent++;
        }

        hartax[pe_x[i]]=curent;
    }

    ante=pe_y[0]-1;
    curent=0;

    for(i=0;i<pe_y.size();i++)
    {
        if(pe_y[i]!=ante)
        {
            ante=pe_y[i];
            curent++;
        }

        hartay[pe_y[i]]=curent;
    }

    for(i=1;i<=n;i++)
    {
        v[i].x=hartax[v[i].x];
        v[i].y=hartay[v[i].y];
    }

    for(i=1;i<=m;i++)
    {
        d[i].a.x=hartax[d[i].a.x];
        d[i].b.x=hartax[d[i].b.x];

        d[i].a.y=hartay[d[i].a.y];
        d[i].b.y=hartay[d[i].b.y];
    }

    for(i=1;i<=n;i++)
        parc.push_back(make_elem(v[i],0,0));

    return 0;
}