Cod sursa(job #2059444)

Utilizator amaliarebAmalia Rebegea amaliareb Data 7 noiembrie 2017 00:32:36
Problema Zoo Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.83 kb
#include <fstream>
#include <algorithm>

#define ll long long

using namespace std;
ifstream f("zoo.in");
ofstream g("zoo.out");
struct punct{ll x, y;} v[16005];
struct drept{punct a1, a2;} drp[100005];
struct miau{ll y, tip, poz;} norm[120005];
struct miau2{ll x, tip, poz;} stari[120005];
ll n, nrnorm, m, i, maxval, nr, aint[700005], sol[100005], qst, qdr, poz;

bool cmp(miau a, miau b)
{
    return a.y < b.y;
}

bool cmp2(miau2 a, miau2 b)
{
    return a.x < b.x || (a.x == b.x && a.tip < b.tip);
}

ll query(ll st, ll dr, ll nod)
{
    ll mid = (st + dr) / 2;
    ll rez = 0;
    if(st >= qst && dr <= qdr) return aint[nod];
    if(qst <= mid) rez += query(st, mid, 2 * nod);
    if(qdr > mid) rez += query(mid + 1, dr, 2 * nod + 1);
    return rez;
}

void update(ll st, ll dr, ll nod)
{
    if(st == dr)
    {
        aint[nod]++;
        return;
    }
    ll mid = (st + dr) / 2;
    if(poz <= mid) update(st, mid, 2 * nod);
    else update(mid + 1, dr, 2 * nod + 1);
    aint[nod] = aint[2 * nod] + aint[2 * nod + 1];
    return;
}

int main()
{
    f >> n;
    for(i = 1; i <= n; i++)
    {
        f >> v[i].x >> v[i].y;
        v[i].x += 2000000001;
        norm[++nrnorm] = {v[i].y, 0, i};
        stari[++nr] = {v[i].x, 1, i};
    }
    f >> m;
    for(i = 1; i <= m; i++)
    {
        f>> drp[i].a1.x >> drp[i].a1.y >> drp[i].a2.x >> drp[i].a2.y;
        drp[i].a1.x += 2000000001;
        drp[i].a2.x += 2000000001;
        norm[++nrnorm] = {drp[i].a1.y, 1, i};
        norm[++nrnorm] = {drp[i].a2.y, 2, i};
        stari[++nr] = {drp[i].a1.x, 0, i};
        stari[++nr] = {drp[i].a2.x, 2, i};
    }
    sort(norm + 1, norm + nrnorm + 1, cmp);
    norm[0] = {-2000000001, 0, 0};
    maxval = 0;
    for(i = 1; i <= nrnorm; i++)
    {
        if(norm[i].y > norm[i - 1].y) maxval++;

        if(norm[i].tip == 0) v[norm[i].poz].y = maxval;
        else if(norm[i].tip == 1) drp[norm[i].poz].a1.y = maxval;
        else drp[norm[i].poz].a2.y = maxval;
    }
    sort(stari + 1, stari + nr + 1, cmp2);
    for(i = 1; i <= nr; i++)
    {
        if(stari[i].tip == 1)
        {
            poz = v[stari[i].poz].y;
            update(1, maxval, 1);
        }
        else if(stari[i].tip == 0)
        {
            qst = 1;
            qdr = drp[stari[i].poz].a1.y - 1;
            if(qdr > 0) sol[stari[i].poz] += query(1, maxval, 1);

            qdr = drp[stari[i].poz].a2.y;
            sol[stari[i].poz] -= query(1, maxval, 1);
        }
        else
        {
            qst = 1;
            qdr = drp[stari[i].poz].a2.y;
            sol[stari[i].poz] += query(1, maxval, 1);

            qdr = drp[stari[i].poz].a1.y - 1;
            if(qdr > 0) sol[stari[i].poz] -= query(1, maxval, 1);
        }
    }
    for(i = 1; i <= m; i++) g << sol[i] << '\n';
    return 0;
}