Cod sursa(job #998665)

Utilizator dariusdariusMarian Darius dariusdarius Data 17 septembrie 2013 20:11:40
Problema Zoo Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.97 kb
#include<set>
#include<unordered_map>
#include<cstdio>
#include<algorithm>
using namespace std;
struct MyQuery {int x1,y1,x2,y2,ans;} q[100005];
struct Solvable_query {int x,y,ind,type;bool semn;} v[416005];
int aib[500000];
void update(int x,int n)
{
	for(int i=x;i<=n;i+=(i&(-i)))
		aib[i]++;
}
int query(int x)
{
	int ans=0;
	for(int i=x;i;i-=(i&(-i)))
		ans+=aib[i];
	return ans;
}
class cmp
{
	public: inline bool operator()(const Solvable_query &a,const Solvable_query &b)
	{
		if(a.x==b.x)
			return a.type<b.type;
		return a.x<b.x;
	}
};
set<int> S;
unordered_map<int,int> NRM;
int normalize(int n)
{
	int ans=0,ind=0;
	for(int i=1;i<=n;i++)
		S.insert(v[i].y);
	for(set<int>::iterator it=S.begin();it!=S.end();it++)
		NRM[*it]=++ind;
	for(int i=1;i<=n;i++)
	{
		v[i].y=NRM[v[i].y];
		ans=max(ans,v[i].y);
	}
	return ans;
}
char buf[7000000];int crs=7000000,sz=7000000;
void getInt(int &n)
{
	n=0;
	while(crs<sz && buf[crs]!='-' && !('0'<=buf[crs] && buf[crs]<='9')) crs++;
	int semn=1;
	if(buf[crs]=='-') semn=-1,crs++;
	while(crs<sz && ('0'<=buf[crs] && buf[crs]<='9')) {n=n*10+buf[crs]-'0';crs++;}
	n*=semn;
}
int main()
{
	freopen("zoo.in","r",stdin);
	freopen("zoo.out","w",stdout);
	int N,n,m;
	fread(buf,1,sz,stdin);
	getInt(n);N=n;
	for(int i=1;i<=n;i++)
		{getInt(v[i].x);getInt(v[i].y);v[i].type=0;}
	getInt(m);
	for(int i=1;i<=m;i++)
	{
		getInt(q[i].x1);
		getInt(q[i].y1);
		getInt(q[i].x2);
		getInt(q[i].y2);
		v[++N].x=q[i].x2;v[N].y=q[i].y2;v[N].type=1;v[N].ind=i;v[N].semn=true;
                v[++N].x=q[i].x2;v[N].y=q[i].y1-1;v[N].type=1;v[N].ind=i;v[N].semn=false;
                v[++N].x=q[i].x1-1;v[N].y=q[i].y2;v[N].type=1;v[N].ind=i;v[N].semn=false;
                v[++N].x=q[i].x1-1;v[N].y=q[i].y1-1;v[N].type=1;v[N].ind=i;v[N].semn=true;
	}
	int MAX=normalize(N);
	sort(v+1,v+N+1,cmp());
	for(int i=1;i<=N;i++)
		if(v[i].type==false)
			update(v[i].y,MAX);
		else
			q[v[i].ind].ans+=(v[i].semn?1:-1)*query(v[i].y);
	for(int i=1;i<=m;i++)
		printf("%d\n",q[i].ans);
	return 0;
}