Pagini recente » Cod sursa (job #3183864) | Cod sursa (job #3282887) | Cod sursa (job #3236483) | Rating Ciprian Nicolae Lazaroaia (donut) | Cod sursa (job #3254297)
// Author: Tanasescu Andrei-Rares
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <stack>
#include <deque>
#include <iomanip>
#include <vector>
#include <cassert>
#pragma GCC optimize("O3")
#define fi first
#define se second
#define pb push_back
#define pf push_front
using namespace std;
ifstream fin ("zoo.in");
ofstream fout ("zoo.out");
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const ll Nmax=16e3+5, Mmax=1e5+5, Vmax=Nmax+Mmax*2, inf=2e9;
int n, m;
vector<int> nx, ny;
pii v[Nmax];
struct event{
int x, y1, y2;
int sgn, ind;
}ev[Mmax*2];
bool cmp(event a, event b){
return a.x<b.x;
}
int sol[Mmax];
struct AIB{
int v[Vmax];
inline void add(int pos){
while (pos<Vmax){
v[pos]++;
pos+=pos&-pos;
}
}
inline int _sum(int pos){
int s=0;
while (pos>0){
s+=v[pos];
pos-=pos&-pos;
}
return s;
}
inline int sum(int l, int r){
return _sum(r)-_sum(l-1);
}
}aib;
int main()
{
// read animals
fin>>n;
for (int i=0; i<n; i++){
fin>>v[i].fi>>v[i].se;
nx.pb(v[i].fi);
ny.pb(v[i].se);
}
// read farms and add them as events
fin>>m;
for (int i=0; i<m; i++){
int x1, y1, x2, y2;
fin>>x1>>y1;
fin>>x2>>y2;
nx.pb(x1); nx.pb(x2);
ny.pb(y1); ny.pb(y2);
ev[i*2]={x1, y1, y2, -1, i};
ev[i*2+1]={x2, y1, y2, 1, i};
}
// normalise
nx.pb(-inf-1); // 1-indexed
ny.pb(-inf-1);
sort(nx.begin(), nx.end());
sort(ny.begin(), ny.end());
for (int i=0; i<n; i++){
v[i].fi=lower_bound(nx.begin(), nx.end(), v[i].fi)-nx.begin();
v[i].se=lower_bound(ny.begin(), ny.end(), v[i].se)-ny.begin();
}
sort(v, v+n);
for (int i=0; i<m*2; i++){
if (i%2==0)
ev[i].x=lower_bound(nx.begin(), nx.end(), ev[i].x)-nx.begin()-1;
else ev[i].x=lower_bound(nx.begin(), nx.end(), ev[i].x)-nx.begin();
ev[i].y1=lower_bound(ny.begin(), ny.end(), ev[i].y1)-ny.begin();
ev[i].y2=lower_bound(ny.begin(), ny.end(), ev[i].y2)-ny.begin();
}
sort(ev, ev+m*2, cmp);
// solve
int indv=0, indq=0;
for (int i=0; i<nx.size(); i++){
while (indv!=n && v[indv].fi==i)
aib.add(v[indv++].se);
while(indq!=m*2 && ev[indq].x==i)
sol[ev[indq++].ind]+=ev[indq].sgn*aib.sum(ev[indq].y1, ev[indq].y2);
}
// print answers
for (int i=0; i<m; i++)
fout<<sol[i]<<'\n';
return 0;
}