Cod sursa(job #2443351)

Utilizator ApostolIlieDanielApostol Daniel ApostolIlieDaniel Data 27 iulie 2019 14:45:40
Problema Zoo Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.01 kb
#include <bits/stdc++.h>
#pragma GCC optimize("O3")

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;
}

ifstream fin ("zoo.in");
ofstream fout ("zoo.out");

int main() {

    ios::sync_with_stdio (false);
    fin.tie (0); fout.tie (0);

    int n;
    fin >> n;
    for (int i = 1; i <= n; i++)
        fin >> 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;
    fin >> q;
    while (q--) {
        int x1, y1, x2, y2;
        fin >> 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 ();
        if (1 <= x1 && x2 <= n)
            fout << query (1, 1, n, x1, x2, y1, y2) << "\n";
        else
            fout << 0 << "\n";
    }
    return 0;
}