Cod sursa(job #2443337)

Utilizator ApostolIlieDanielApostol Daniel ApostolIlieDaniel Data 27 iulie 2019 14:30:52
Problema Zoo Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.92 kb
#include <bits/stdc++.h>

using namespace std;

struct Point {
    int x;
    int y;
};

bool cmp (Point a, Point b) {
    if (a.x != b.x)
        return a.x < b.x;
    return a.y < b.y;
}

const int N = 16000;

vector <int> seg[1 + 4 * N];

#define pb push_back

Point a[1 + N];

void build (int node, int l, int r) {
    if (l == r) {
        seg[node].pb (a[l].y);
        return;
    }
    int mid = (l + r) / 2;
    build (node * 2, l, mid);
    build (node * 2 + 1, mid + 1, r);
    seg[node].resize (seg[2 * node].size () + seg[2 * node + 1].size ());
    merge (seg[2 * node].begin (), seg[2 * node].end (), seg[2 * node + 1].begin (), seg[2 * node + 1].end (), seg[node].begin ());
}

int query (int node, int l, int r, int x1, int x2, int y1, int y2) {
    if (x1 <= l && r <= x2) {
        return upper_bound (seg[node].begin (), seg[node].end (), y2) - lower_bound (seg[node].begin (), seg[node].end (), y1);
    }
    int mid = (l + r) / 2;
    int ans = 0;
    if (mid >= x1)
        ans += query (node * 2, l, mid, x1, x2, y1, y2);
    if (mid + 1 <= x2)
        ans += query (node * 2 + 1, mid + 1, r, x1, x2, y1, y2);
    return ans;
}

int main() {
    freopen ("zoo.in", "r", stdin);
    freopen ("zoo.out", "w", stdout);

    ios::sync_with_stdio (false);
    cin.tie (0); cout.tie (0);

    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i].x >> a[i].y;

    sort (a + 1, a + n + 1, cmp);

    build (1, 1, n);
    vector <int> v;
    for (int i = 1; i <= n; i++)
        v.pb (a[i].x);
    sort (v.begin (), v.end ());
    int q;
    cin >> q;
    while (q--) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        x1 = lower_bound (v.begin (), v.end (), x1) - v.begin () + 1;
        x2 = upper_bound (v.begin (), v.end (), x2) - v.begin ();
        cout << query (1, 1, n, x1, x2, y1, y2) << "\n";
    }
    return 0;
}