Cod sursa(job #3162120)

Utilizator YosifIosif Andrei Stefan Yosif Data 28 octombrie 2023 13:30:04
Problema Zoo Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 6.01 kb
#include <bits/stdc++.h>
using namespace std;

class input {
private:
    FILE* fin;
    char* t;
    int sp;
    const int sz = 1000;

    char read()
    {
        if (sp == sz)
        {
            fread(t, 1, sz, fin);
            sp = 0;
            return t[sp++];
        }
        else
            return t[sp++];
    }
public:
    input(string name)
    {
        fin = fopen(name.c_str(), "r");
        sp = sz;
        t = new char[sz]();
    }

    void close()
    {
        fclose(fin);
    }

    void open(const char* name)
    {
        fin = fopen(name, "r");
        sp = sz;
        t = new char[sz]();
    }

    input& operator >> (int& n)
    {
        char c = read();

        while (c == ' ' || c == '\n')
            c = read();

        n = 0;

        int sng = 1;

        if (c == '-')
            sng = -1, c = read();

        while (c != '\0' && isdigit(c))
            n = n * 10 + (c - '0'), c = read();

        n *= sng;

        return *this;
    }

    input& operator >> (char& s)
    {
        char c = read();

        while (c != '\0' && c == '\n')
            c = read();

        s = c;

        return *this;
    }

    input& operator >> (long long& n)
    {
        char c = read();

        while (c == ' ' || c == '\n')
            c = read();

        n = 0;

        int sng = 1;

        if (c == '-')
            sng = -1, c = read();

        while (c != '\0' && isdigit(c))
            n = n * 10 + (c - '0'), c = read();

        n *= sng;

        return *this;
    }

    void getline(string& s)
    {
        char c = read();
        s = "";

        while (c != '\0' && c != '\n')
            s += c, c = read();
    }

    input& operator >> (string& s)
    {
        char c;
        c = read();
        s = "";

        while (c == '\n' || c == ' ')
            c = read();

        while (c != '\n' && c != '\0' && c != ' ')
            s += c, c = read();

        return *this;
    }

    input& operator >> (char* s)
    {
        char c;
        c = read();
        int i = 0;

        while (c == '\n' || c == ' ')
            c = read();

        while (c != '\n' && c != '\0' && c != ' ')
            s[i++] = c, c = read();

        return *this;
    }
};
class output {
private:
    FILE* fout;
    char* t;
    int sp;
    const int sz = 1000;

    void write(char c)
    {
        if (sp == sz)
        {
            fwrite(t, 1, sz, fout);
            sp = 0;
            t[sp++] = c;
        }
        else
            t[sp++] = c;
    }

public:
    output(string name)
    {
        fout = fopen(name.c_str(), "w");
        sp = 0;
        t = new char[sz]();
    }

    ~output()
    {
        fwrite(t, 1, sp, fout);
    }

    output& operator << (int n)
    {
        if (n < 0)
        {
            write('-');
            n *= -1;
        }
        if (n <= 9)
            write(char(n + '0'));
        else
        {
            (*this) << (n / 10);
            write(char(n % 10 + '0'));
        }

        return *this;
    }

    output& operator << (char c)
    {
        write(c);

        return *this;
    }

    output& operator << (const char* s)
    {
        int i = 0;

        while (s[i] != '\0')
            write(s[i++]);

        return *this;
    }

    output& operator << (long long n)
    {
        if (n < 0)
        {
            write('-');
            n *= -1;
        }
        if (n < 10)
            write(char(n + '0'));
        else
        {
            (*this) << (n / 10);
            write(char(n % 10 + '0'));
        }

        return *this;
    }

    output& operator << (string s)
    {
        for (auto i : s)
            write(i);

        return *this;
    }

    void precizion(double x, int nr)
    {
        int p = int(floor(x));

        *this << p;

        if (nr == 0)
            return;

        write('.');

        for (int i = 1; i <= nr; i++)
        {
            x -= floor(x);
            x *= 10;

            write(int(x) + '0');
        }
    }
};

string file = "zoo";
input fin(file + ".in");
output fout(file + ".out");

int n, m;
pair <int, int> v[100001];
vector <int> t[100001];

void build(int i = 1, int l = 1, int r = n) {

    if (l == r) {

        t[i].resize(1);
        t[i][0] = v[l].second;
        return;
    }

    int m = (l + r) >> 1;
    int aux = (i << 1);

    build(aux, l, m);
    build(aux + 1, m + 1, r);

    vector <int>::iterator it1, it2;
    it1 = t[aux].begin();
    it2 = t[aux + 1].begin();

    while (it1 != t[aux].end() && it2 != t[aux + 1].end())
        if (*it1 < *it2)
            t[i].push_back(*it1), it1++;
        else
            t[i].push_back(*it2), it2++;

    while (it1 != t[aux].end())
        t[i].push_back(*it1), it1++;

    while (it2 != t[aux + 1].end())
        t[i].push_back(*it2), it2++;
}

int get(int x1, int y1, int x2, int y2, int i = 1, int l = 1, int r = n) {

    if (x2 < v[l].first || v[r].first < x1)
        return 0;

    if (x1 <= v[l].first && v[r].first <= x2) {

        int Left = 0, Right = t[i].size() - 1, pos1 = -1, pos2 = -1;

        while (Left <= Right) {

            int mid = (Left + Right) >> 1;

            if (t[i][mid] >= y1) {

                pos1 = mid;
                Right = mid - 1;
            }
            else
                Left = mid + 1;
        }

        if (pos1 == -1)
            return 0;

        Left = pos1;
        Right = t[i].size() - 1;

        while (Left <= Right) {

            int mid = (Left + Right) >> 1;

            if (t[i][mid] <= y2) {

                pos2 = mid;
                Left = mid + 1;
            }
            else
                Right = mid - 1;
        }

        return pos2 - pos1 + 1;
    }

    int m = (l + r) >> 1;

    return get(x1, y1, x2, y2, (i << 1), l, m) + get(x1, y1, x2, y2, (i << 1) + 1, m + 1, r);
}

int main() {

    fin >> n;

    for (int i = 1; i <= n; i++)
        fin >> v[i].first >> v[i].second;

    sort(v + 1, v + n + 1);
    build();

    fin >> m;

    for (int i = 1; i <= m; i++) {

        int x1, y1, x2, y2;
        fin >> x1 >> y1 >> x2 >> y2;

        fout << get(x1, y1, x2, y2) << '\n';
    }

    return 0;
}