Pagini recente » Cod sursa (job #2335721) | Cod sursa (job #2781493) | Cod sursa (job #898899) | Cod sursa (job #677323) | Cod sursa (job #2964187)
#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;
}