Cod sursa(job #2964187)

Utilizator Chris_BlackBlaga Cristian Chris_Black Data 12 ianuarie 2023 16:30:05
Problema Zoo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.37 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <tuple>
using namespace std;
ifstream cin("zoo.in");
ofstream cout("zoo.out");

struct Point {
	int x, y;
};

vector<Point> Points, Queries;
vector<int> values;
vector<int> answers;

int normalize(int value)
{
    return distance(values.begin(),lower_bound(values.begin(),values.end(),value)) + 1;
}

template<typename T>
struct bit
{
    int N;
    vector<vector<T>> tree;
    bit() {}
    bit(int size)
    {
        N = size;
        tree = vector<vector<T>>(size+1);
    }
    bit& operator = (const bit &DS)
    {
        N = DS.N;
        tree = DS.tree;
        return *this;
    }
    int lsb(int i)
    {
        return i&(-i);
    }
    void insert(int x,int y)
    {
        for(int i = x;i<=N;i += lsb(i))
            tree[i].push_back(y);
    }
    void sortAll()
    {
        for(int i=1;i<=N;++i)
            sort(tree[i].begin(),tree[i].end());
    }
    int query(int x,int y)
    {
        int ret = 0;
        for(int i=x;i;i-=lsb(i))
            ret += distance(tree[i].begin(),lower_bound(tree[i].begin(),tree[i].end(),y+1));
        return ret;
    }
};

int N,M;
bit<int> DS;

int main()
{
    cin>>N;
    Points = vector<Point>(N);
    for(auto &p : Points)
    {
        cin>>p.x>>p.y;
    }
    cin>>M;
    for(int i=0;i<M;++i)
    {
        int x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;

        Queries.push_back({x2,y2});
        Queries.push_back({x1-1,y2});
        Queries.push_back({x2,y1-1});
        Queries.push_back({x1-1,y1-1});
    }

    for(auto &p : Points)
        values.push_back(p.x);
    for(auto &q : Queries)
        values.push_back(q.x);

    sort(values.begin(),values.end());
    values.erase(unique(values.begin(),values.end()),values.end());

    for(auto &p : Points)
        p.x = normalize(p.x);
    for(auto &q : Queries)
        q.x = normalize(q.x);

    DS = bit<int>(values.size());

    for(auto &p : Points)
        DS.insert(p.x,p.y);

    DS.sortAll();

    for(int i=0;i<Queries.size();i+=4)
    {
        int a = DS.query(Queries[i].x,Queries[i].y);
        int b = DS.query(Queries[i+1].x,Queries[i+1].y);
        int c = DS.query(Queries[i+2].x,Queries[i+2].y);
        int d = DS.query(Queries[i+3].x,Queries[i+3].y);

        cout<<a-b-c+d<<'\n';
    }
    return 0;
}