Pagini recente » Cod sursa (job #2891465) | Cod sursa (job #2969400) | Cod sursa (job #3222032) | Cod sursa (job #2856327) | Cod sursa (job #3255375)
#include <fstream>
#include <map>
#include <unordered_map>
#include <algorithm>
using namespace std;
struct el
{
int sw; //0 daca e animal, 1 daca e margine de query
int x, y1, y2;
int id, sf;
};
ifstream in("zoo.in");
ofstream out("zoo.out");
int n, m, p, cnt;
pair<int, int> v[16005];
pair<pair<int, int>, pair<int, int>> w[100005];
map<int, int> mp;
unordered_map<int, int> norm;
el vec[216005];
int aib[216005];
int ans[100005];
bool cmp(const el &a, const el &b)
{
if(a.x == b.x)
{
return a.sw < b.sw;
}
else
{
return a.x < b.x;
}
}
void update(int x, int poz)
{
for(int i = poz; i<=cnt; i+=(i&-i))
{
aib[i] += x;
}
}
int query(int poz)
{
int sum = 0;
for(int i = poz ; i>=1; i-=(i&-i))
{
sum += aib[i];
}
return sum;
}
int main()
{
in>>n;
for(int i = 1; i<=n; i++)
{
in>>v[i].first>>v[i].second;
mp[v[i].second] = 1;
}
in>>m;
for(int i = 1; i<=m; i++)
{
in>>w[i].first.first>>w[i].first.second>>w[i].second.first>>w[i].second.second;
mp[w[i].first.second] = 1;
mp[w[i].second.second] = 1;
}
cnt = 0;
for(auto it: mp)
{
cnt++;
norm[it.first] = cnt;
}
for(int i = 1; i<=n; i++)
{
v[i].second = norm[v[i].second];
//out<<v[i].first<<" "<<v[i].second<<'\n';
p++;
vec[p] = {0, v[i].first, v[i].second, 0, 0, 0};
}
for(int i = 1; i<=m; i++)
{
w[i].first.second = norm[w[i].first.second];
w[i].second.second = norm[w[i].second.second];
//out<<w[i].first.first<<" "<<w[i].first.second<<" "<<w[i].second.first<<" "<<w[i].second.second<<'\n';
p++;
vec[p] = {1, w[i].first.first - 1, w[i].first.second, w[i].second.second, i, 0};
p++;
vec[p] = {1, w[i].second.first, w[i].first.second, w[i].second.second, i, 1};
}
sort(vec + 1, vec + p + 1, cmp);
for(int i = 1; i<=p; i++)
{
if(vec[i].sw == 0)
{
update(1, vec[i].y1);
}
else
{
int s = query(vec[i].y2) - query(vec[i].y1 - 1);
if(vec[i].sf == 0)
{
ans[vec[i].id] -= s;
}
else
{
ans[vec[i].id] += s;
}
}
}
for(int i = 1; i<=m; i++)
{
out<<ans[i]<<'\n';
}
return 0;
}