Pagini recente » Cod sursa (job #431450) | Cod sursa (job #2629451) | Cod sursa (job #567920) | Cod sursa (job #405225) | Cod sursa (job #1166025)
#include <fstream>
#include <set>
#include <vector>
#include <algorithm>
#define MAXN 16005
#define MAXM 100005
#define MAXC 100
using namespace std;
ifstream f("zoo.in");
ofstream g("zoo.out");
struct event{
short int tip;
int t,nr;};
int n,m,x,cnt,ny,aib[2*MAXM+MAXN],sol[MAXM];
set<int> sy;
set<int>::iterator it;
pair<int,int> pct[MAXN];
pair< pair<int,int>, pair<int,int> > dreptunghi[MAXM];
char s[MAXC];
event aux;
vector<event> ev;
vector<int> vy;
vector<int>::iterator it2;
inline void update_aib(int p);
inline int query_aib(int p);
inline int get_int();
inline bool Comp(event p,event q){
if(p.t==q.t)
return p.tip<q.tip;
return p.t<q.t;};
int main()
{
int i;
f>>n;
f.getline(s,MAXC,'\n');
aux.tip=1;
for(i=1;i<=n;i++){
f.getline(s,MAXC,'\n');
cnt=0;
pct[i].first=get_int();
pct[i].second=get_int();
sy.insert(pct[i].second);
aux.t=pct[i].first;
aux.nr=i;
ev.push_back(aux);}
f>>m;
f.getline(s,MAXC,'\n');
for(i=1;i<=m;i++){
f.getline(s,MAXC,'\n');
cnt=0;
dreptunghi[i].first.first=get_int();
dreptunghi[i].first.second=get_int();
dreptunghi[i].second.first=get_int();
dreptunghi[i].second.second=get_int();
sy.insert(dreptunghi[i].first.second);
sy.insert(dreptunghi[i].second.second);
aux.nr=i;
aux.tip=0;
aux.t=dreptunghi[i].first.first;
ev.push_back(aux);
aux.tip=2;
aux.t=dreptunghi[i].second.first;
ev.push_back(aux);}
for(it=sy.begin();it!=sy.end();it++)
vy.push_back(*it);
ny=vy.size();
for(i=1;i<=n;i++)
pct[i].second=(lower_bound(vy.begin(),vy.end(),pct[i].second)-vy.begin())+1;
for(i=1;i<=m;i++){
dreptunghi[i].first.second=(lower_bound(vy.begin(),vy.end(),dreptunghi[i].first.second)-vy.begin())+1;
dreptunghi[i].second.second=(lower_bound(vy.begin(),vy.end(),dreptunghi[i].second.second)-vy.begin())+1;}
sort(ev.begin(),ev.end(),Comp);
for(i=0;i<ev.size();i++){
aux=ev[i];
if(aux.tip==1){
update_aib(pct[aux.nr].second);
continue;}
x=query_aib(dreptunghi[aux.nr].second.second)-query_aib(dreptunghi[aux.nr].first.second-1);
if(aux.tip)
sol[aux.nr]+=x;
else
sol[aux.nr]-=x;}
for(i=1;i<=m;i++)
g<<sol[i]<<'\n';
f.close();
g.close();
return 0;
}
inline int get_int(){
int semn;
if(s[cnt]=='-'){
semn=-1;
++cnt;}
else
semn=1;
x=s[cnt++]-'0';
while(s[cnt]>='0'&&s[cnt]<='9')
x=x*10+s[cnt++]-'0';
cnt++;
return semn*x;}
inline void update_aib(int p){
while(p<=ny){
aib[p]++;
p+=(p&(-p));}}
inline int query_aib(int p){
int S=0;
while(p){
S+=aib[p];
p-=(p&(-p));}
return S;}