Cod sursa(job #2455990)

Utilizator mihai50000Mihai-Cristian Popescu mihai50000 Data 13 septembrie 2019 11:40:14
Problema Zoo Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.9 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("zoo.in");
ofstream fout("zoo.out");

const long long Bound = 2e9;

#define int long long

struct SegmentTree
{
    int l;
    int r;

    vector <int> v;

    SegmentTree *st;
    SegmentTree *dr;

    SegmentTree()
    {
        st = nullptr;
        dr = nullptr;

        l = 0;
        r = 0;

        v.clear();
    }

    void Expand(int dir)
    {
        SegmentTree *now = this;

        if(dir == 0)
        {
            if(now -> st == nullptr)
            {
                now -> st = new SegmentTree;
                now -> st -> l = now -> l;
                now -> st -> r = (now -> l + now -> r) / 2;
            }
        }
        else
        {
            if(now -> dr == nullptr)
            {
                now -> dr = new SegmentTree;
                now -> dr -> l = (now -> l + now -> r) / 2 + 1;
                now -> dr -> r = now -> r;
            }
        }
    }

    void update(int linie, int col)
    {
        SegmentTree *now = this;

        now -> v.push_back(col);

        if(l == r)
        {
            return ;
        }

        int mid = (now -> l + now -> r) / 2;

        if(linie <= mid)
        {
            now -> Expand(0);
            now -> st -> update(linie, col);
        }
        else
        {
            now -> Expand(1);
            now -> dr -> update(linie, col);
        }
    }

    int get(vector <int> v, int x, int y)
    {
        if(v.size() == 0)
            return 0;

        int n = v.size();
        int l = 0;
        int r = n - 1;

        int itr1 = 0;
        int itr2 = 0;

        if(v[r] < x)
            return 0;

        if(v[l] > y)
            return 0;

        while(l <= r)
        {
            int mid = (l + r) / 2;

            if(v[mid] < x)
            {
                l = mid + 1;
            }
            else
            {
                itr1 = mid;
                r = mid - 1;
            }
        }

        if(v[itr1] > y)
            return 0;

        l = 0;
        r = n - 1;

        while(l <= r)
        {
            int mid = (l + r) / 2;

            if(v[mid] > y)
            {
                r = mid - 1;
            }
            else
            {
                l = mid + 1;
                itr2 = mid;
            }
        }

        if(v[itr2] < x)
            return 0;

        return itr2 - itr1 + 1;
    }

    int query(int x1, int y1, int x2, int y2)
    {
        SegmentTree *now = this;

        int l = now -> l;
        int r = now -> r;

        if(x1 <= l && r <= x2)
        {
            return get(now -> v, y1, y2);
        }

        int mid = (l + r) / 2;

        int sum = 0;

        if(x1 <= mid && now -> st != nullptr)
            sum += now -> st -> query(x1, y1, x2, y2);

        if(x2 > mid && now -> dr != nullptr)
            sum += now -> dr -> query(x1, y1, x2, y2);

        return sum;
    }

    void aranjare()
    {
        SegmentTree *now = this;

        sort(now -> v.begin(), now -> v.end());

        if(now -> st != nullptr)
            now -> st -> aranjare();

        if(now -> dr != nullptr)
            now -> dr -> aranjare();
    }

};

SegmentTree *arb = new SegmentTree;

void upd(int &x)
{
    x = x + Bound + 1;
}

main()
{
    arb -> l = 1;
    arb -> r = Bound * 2 + 1;

    int n;
    fin >> n;

    while(n--)
    {
        int x, y;
        fin >> x >> y;

        upd(x);
        upd(y);

        arb -> update(x, y);
    }

    arb -> aranjare();

    fin >> n;

    while(n--)
    {
        int x1, y1, x2, y2;
        fin >> x1 >> y1 >> x2 >> y2;

        upd(x1);
        upd(y1);
        upd(x2);
        upd(y2);

        int p = arb -> query(x1, y1, x2, y2);

        fout << p << '\n';
    }
}