Cod sursa(job #2327694)

Utilizator MAXIMILLIANMUSOHYEAHYEAH MAXIMILLIANMUS Data 24 ianuarie 2019 20:07:34
Problema Zoo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.84 kb
#include <bits/stdc++.h>
 
#define ios ios::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL)
 
#define pb push_back
 
#define mp make_pair
 
#define x first
 
#define y second
 
#define enter cout << '\n'
 
 
 
using namespace std;
 
 
 
typedef long long ll;
 
typedef pair <int, int> pii;
 
typedef pair <ll, ll> pll;
 
typedef vector <int> vi;
 
typedef vector <pii> vii;
 
typedef vector <ll> vl;
 
typedef vector <pll> vll;
 
typedef queue <int> qi;
 
typedef queue <pii> qii;
 
typedef queue <ll> ql;
 
typedef queue <pll> qll;
 
 
 
const int INF = SHRT_MAX - 2;
 
const int MOD = 100019;
 
const int EPSILON = 0.0000000001;
 
const short NMAX = 16000 + 5;
 
 
 
ifstream fin("zoo.in");
 
ofstream fout("zoo.out");
 
/*
{1}
struct Point
{1}
{
{1}
    int x, y;
{1}
{1}
{1}
    Point()
{1}
    {
{1}
        x = y = 0;
{1}
    }
{1}
{1}
{1}
    Point(int _x, int _y)
{1}
    {
{1}
        x = _x;
{1}
        y = _y;
{1}
    }
{1}
{1}
{1}
    bool operator <(const Point &arg) const
{1}
    {
{1}
        if (x == arg.x)
{1}
            return y < arg.y;
{1}
        return x < arg.x;
{1}
    }
{1}
};
{1}
*/
 
 
 
typedef pair<int, int> Point;
 
 
 
vi aint[5 * NMAX];
 
int n, m;
 
Point v[NMAX];
 
 
 
void build(int node, int st, int dr)
 
{
 
    for (int i = st; i <= dr; ++i)
 
        aint[node].pb(v[i].y);
 
    sort(aint[node].begin(), aint[node].end());
 
 
 
    if (st >= dr) return;
 
 
 
    int mijl = (st + dr) / 2;
 
    build(2 * node, st, mijl);
 
    build(2 * node + 1, mijl + 1, dr);
 
}
 
 
 
int query(int node, int st, int dr, int left, int right, int y1, int y2)
 
{
 
    if (left <= st && dr <= right)
 
        return upper_bound(aint[node].begin(), aint[node].end(), y2) - lower_bound(aint[node].begin(), aint[node].end(), y1);
 
 
 
    int ans = 0, mijl = (st + dr) / 2;
 
    if (left <= mijl) ans += query(2 * node, st, mijl, left, right, y1, y2);
 
    if (mijl < right) ans += query(2 * node + 1, mijl + 1, dr, left, right, y1, y2);
 
 
 
    return ans;
 
}
 
 
 
void write()
 
{
 
    int x1, x2, y1, y2, left, right;
 
 
 
    fin >> m;
 
    for (int i = 1; i <= m; ++i)
 
    {
 
        fin >> x1 >> y1 >> x2 >> y2;
 
 
 
        left = lower_bound(v + 1, v + n + 1, Point(x1, y1)) - v;
 
        right = upper_bound(v + 1, v + n + 1, Point(x2, y2)) - v - 1;
 
 
 
        if (left > right) fout << "0\n";
 
        else fout << query(1, 1, n, left, right, y1, y2) << '\n';
 
    }
 
}
 
 
 
void read()
 
{
 
    fin >> n;
 
    for (int i = 1; i <= n; ++i)
 
        fin >> v[i].x >> v[i].y;
 
    sort(v + 1, v + n + 1);
 
}
 
 
 
int main()
 
{
 
    read();
 
    build(1, 1, n);
 
    write();
 
 
 
    return 0;
 
}