Cod sursa(job #2521771)

Utilizator rares404AlShaytan - Balasescu Rares rares404 Data 11 ianuarie 2020 14:41:18
Problema Zoo Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 6 kb
#include <bits/stdc++.h>
#define debug(x) std::cerr << (#x) << " : " << x << '\n'
#pragma optimize("O3")

FILE *out = fopen ("zoo.out", "w") ;

/// ~ using int = long long ;

const int INF = 2e9 + 5 ;

struct Point {
        int x, y ;
        Point() {
                x = y = -INF ;
        }
        Point (int _x, int _y) {
                this ->x = _x ;
                this ->y = _y ;
        }
        bool operator < (const Point &aux) const {
                if (this ->x == aux.x) {
                        return this ->y < aux.y ;
                }
                return this ->x < aux.x ;
        }
};

typedef std::vector<int> VI ;

void viz (VI a) {
        for (auto it : a) {
                std::cerr << it << ' ' ;
        }
        std::cerr << '\n' ;
}

class InputReader {
public:
        InputReader() {}
        InputReader (const char *file_name) {
                input_file = fopen (file_name, "r");
                cursor = 0;
                fread (buffer, SIZE, 1, input_file);
        }
        inline InputReader &operator >> (int &n) {
                while ((buffer[cursor] < '0' || buffer[cursor] > '9') && buffer[cursor] != '-') {
                        advance();
                }
                int sgn = 1 ;
                if (buffer[cursor] == '-') {
                        sgn = -1 ;
                        advance() ;
                }
                n = 0;
                while ('0' <= buffer[cursor] && buffer[cursor] <= '9') {
                        n = n * 10 + buffer[cursor] - '0';
                        advance();
                }
                n *= sgn ;
                return *this;
        }
private:
        FILE *input_file;
        static const int SIZE = 1 << 17;
        int cursor;
        char buffer[SIZE];
        inline void advance() {
                ++ cursor;
                if (cursor == SIZE) {
                        cursor = 0;
                        fread (buffer, SIZE, 1, input_file);
                }
        }
};

namespace zoo {
VI merge (VI a, VI b) {
        VI ret ;
        int fi (0), se (0) ;
        for (; fi < a.size() || se < b.size() ;) {
                if (fi != a.size() && a[fi] < b[se] || se == b.size()) {
                        ret.push_back (a[fi]) ;
                        fi ++ ;
                } else if (se != b.size() && a[fi] > b[se] || fi == a.size()) {
                        ret.push_back (b[se]) ;
                        se ++ ;
                } else {
                        ret.push_back (a[fi]) ;
                        fi ++ ;
                }
        }
        return ret ;
}
}

const int MAXN = 16e3 ;

std::vector<Point> points ;
VI abscisa ;
VI ordonata ;

std::vector<int> aint[MAXN << 2] ;

int leftChild (int node) {
        return node << 1 ;
}

int rightChild (int node) {
        return (node << 1) + 1 ;
}

int query (int node, int left, int right, int leftInt, int rightInt, int leftVal, int rightVal) {
        if (left == leftInt && right == rightInt) {
                /// ~ viz(aint[node]) ;
                int fi = std::upper_bound (aint[node].begin(), aint[node].end(), rightVal) - aint[node].begin() - 1 ;
                int se = std::lower_bound (aint[node].begin(), aint[node].end(), leftVal) - aint[node].begin() ;
                return fi - se + 1 ;
        }
        int mid ( (left + right) >> 1) ;
        if (rightInt <= mid) {
                return query (leftChild (node), left, mid, leftInt, rightInt, leftVal, rightVal) ;
        }
        if (mid + 1 <= leftInt) {
                return query (rightChild (node), mid + 1, right, leftInt, rightInt, leftVal, rightVal) ;
        }
        int fi = query (leftChild (node), left, mid, leftInt, mid, leftVal, rightVal) ;
        int se = query (rightChild (node), mid + 1, right, mid + 1, rightInt, leftVal, rightVal) ;
        return fi + se ;
}

void build (int node, int left, int right) {
        if (left == right) {
                aint[node] = {ordonata[left]} ;
                /* ~ debug(ordonata[left]) ;
                   ~ debug(left) ;
                   ~ std::cerr << node << " : " ; viz(aint[node]) ;*/
                return ;
        }
        int mid ( (left + right) >> 1) ;
        build (leftChild (node), left, mid) ;
        build (rightChild (node), mid + 1, right) ;
        /// ~ aint[node] = zoo::merge(aint[leftChild(node)], aint[rightChild(node)]) ;
        aint[node].resize (aint[2 * node].size() + aint[2 * node + 1].size()) ;
        std::merge (aint[2 * node].begin(), aint[2 * node].end(), aint[2 * node + 1].begin(), aint[2 * node + 1].end(), aint[node].begin());
        /// ~ std::cerr << node << " : " ; viz(aint[node]) ;
}

int main() {
        int n ;
        int x, y ;
        int querys ;
        InputReader in("zoo.in") ;
        in >> n ;
        points.resize (n + 1) ;
        for (int i = 1 ; i <= n ; ++ i) {
                in >> x >> y ;
                points[i] = Point (x, y) ;
        }
        std::sort (begin (points), end (points)) ;
        for (int i = 0 ; i < n ; ++ i) {
                abscisa.push_back (points[i + 1].x) ;
                ordonata.push_back (points[i + 1].y) ;
        }

        build (1, 0, n - 1) ;

        in >> querys ;
        Point leftDown, rightUp ;
        /// ~ viz(abscisa) ;
        for (int i = 1 ; i <= querys ; ++ i) {
                in >> x >> y ;
                leftDown = Point (x, y) ;
                in >> x >> y ;
                rightUp = Point (x, y) ;
                int leftLimit = std::lower_bound (abscisa.begin(), abscisa.end(), std::min (leftDown.x, rightUp.x)) - abscisa.begin() ;
                int rightLimit = std::upper_bound (abscisa.begin(), abscisa.end(), std::max (leftDown.x, rightUp.x)) - abscisa.begin() - 1 ;
                int ans = query (1, 0, n - 1, leftLimit, rightLimit, std::min (leftDown.y, rightUp.y), std::max (leftDown.y, rightUp.y)) ;
                fprintf (out, "%d\n", ans) ;
        }
}