Cod sursa(job #3139267)

Utilizator AnonymousUserBogdan Ionelia AnonymousUser Data 26 iunie 2023 19:21:00
Problema Zoo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.53 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;
const int N = 16000;
vector<int> segment_tree[4*N+1];
vector<int> list[N+1];
pair<int, int> points[N+1];

void build(int node, int left, int right)
{
    if(left == right)
    {
        swap(segment_tree[node], list[left]);
        sort(segment_tree[node].begin(), segment_tree[node].end());
    }
    else
    {
        int m = (left + right) / 2;
        build(node*2, left, m);
        build(node*2+1, m+1, right);
        merge(segment_tree[node*2].begin(), segment_tree[node*2].end(), segment_tree[node*2+1].begin(), segment_tree[node*2+1].end(), back_inserter(segment_tree[node]));
    }
}

int query(int node, int left, int right, int x_left, int x_right, int y_left, int y_right)
{
    if(x_left <= left && right <= x_right)
        return upper_bound(segment_tree[node].begin(), segment_tree[node].end(), y_right) - lower_bound(segment_tree[node].begin(), segment_tree[node].end(), y_left);
    else
    {
        int m = (left + right) / 2;
        if(x_right <= m)
            return query(node*2, left, m, x_left, x_right, y_left, y_right);
        if(m+1 <= x_left)
            return query(node*2+1, m+1, right, x_left, x_right, y_left, y_right);
        int left_ans = query(node*2, left, m, x_left, x_right, y_left, y_right);
        int right_ans = query(node*2+1, m+1, right, x_left, x_right, y_left, y_right);
        return left_ans + right_ans;
    }
}

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

    vector<int> coord_X;
    int n, m;
    long long x1, y1, x2, y2;
    fin >> n;
    for(int i = 1; i <= n; ++i)
        fin >> points[i].first >> points[i].second, coord_X.push_back(points[i].first);
    sort(coord_X.begin(), coord_X.end());
    coord_X.resize(unique(coord_X.begin(), coord_X.end()) - coord_X.begin());
    for(int i = 1; i <= n; ++i)
    {
        points[i].first = lower_bound(coord_X.begin(), coord_X.end(), points[i].first) - coord_X.begin() + 1;
        list[points[i].first].push_back(points[i].second);
    }
    build(1, 1, coord_X.size());
    fin >> m;
    while(m--)
    {
        fin >> x1 >> y1 >> x2 >> y2;
        x1 = lower_bound(coord_X.begin(), coord_X.end(), x1) - coord_X.begin() + 1;
        x2 = upper_bound(coord_X.begin(), coord_X.end(), x2) - coord_X.begin();
        if(x1 > x2)
            fout << 0 << '\n';
        else
            fout << query(1, 1, coord_X.size(), x1, x2, y1, y2) << '\n';
    }
    return 0;
}