Cod sursa(job #2059447)

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

#define ll long long

using namespace std;
struct punct{ll x, y;} v[16005];
struct drept{punct a1, a2;} drp[100005];
struct miau{int y, tip, poz;} norm[400005];
struct miau2{int x, tip, poz;} stari[400005];
ll aint[1200005], sol[100005];
int n, nrnorm, m, i, maxval, nr, qst, qdr, poz;


class InParser {
private:
    FILE *fin;
    char *buff;
    int sp;

    char read_ch() {
        ++sp;
        if (sp == 4096) {
            sp = 0;
            fread(buff, 1, 4096, fin);
        }
        return buff[sp];
    }

public:
    InParser(const char* nume) {
        fin = fopen(nume, "r");
        buff = new char[4096]();
        sp = 4095;
    }

    InParser& operator >> (int &n) {
        char c;
        while (!isdigit(c = read_ch()) && c != '-');
        int sgn = 1;
        if (c == '-') {
            n = 0;
            sgn = -1;
        } else {
            n = c - '0';
        }
        while (isdigit(c = read_ch())) {
            n = 10 * n + c - '0';
        }
        n *= sgn;
        return *this;
    }

    InParser& operator >> (long long &n) {
        char c;
        n = 0;
        while (!isdigit(c = read_ch()) && c != '-');
        long long sgn = 1;
        if (c == '-') {
            n = 0;
            sgn = -1;
        } else {
            n = c - '0';
        }
        while (isdigit(c = read_ch())) {
            n = 10 * n + c - '0';
        }
        n *= sgn;
        return *this;
    }
};

InParser f("zoo.in");
ofstream g("zoo.out");

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

int query(int st, int dr, int nod)
{
    int mid = (st + dr) / 2;
    int 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(int st, int dr, int nod)
{
    if(st == dr)
    {
        aint[nod]++;
        return;
    }
    int 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;
        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;
        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;
}