Cod sursa(job #2521079)

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

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

using i64 = long long ;

const i64 INF = 2e9 + 5 ;

struct Point {
        i64 x, y ;
        Point() {
                x = y = -INF ;
        }
        Point(i64 _x, i64 _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<i64> VI ;

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

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 ;

VI 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, i64 leftVal, i64 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)]) ;
        /// ~ std::cerr << node << " : " ; viz(aint[node]) ;
}

int main() {
        int n ;
        i64 x, y ;
        int querys ;
        fscanf(in, "%d", &n) ; points.resize(n + 1) ;
        for (int i = 1 ; i <= n ; ++ i) {
                fscanf(in, "%lld %lld", &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) ;

        fscanf(in, "%d", &querys) ;
        Point leftDown, rightUp ;
        /// ~ viz(abscisa) ;
        for (int i = 1 ; i <= querys ; ++ i) {
                fscanf(in, "%lld %lld ", &x, &y) ; leftDown = Point(x, y) ;
                fscanf(in, "%lld %lld ", &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) ;
        }
}