Cod sursa(job #1002874)

Utilizator dariusdariusMarian Darius dariusdarius Data 28 septembrie 2013 23:06:54
Problema Zoo Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.29 kb
#include<vector>
#include<cstdio>
#include<algorithm>
using namespace std;
int ans[100005];
struct Solvable_query {int x,y,ind;bool type,semn;} v[416005];
int aib[500005];
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;
const int hmod=73013;
int aux[416005];
vector< pair<int,int> > H[hmod];
int normalize(int n)
{
    int ans=0,ind=0;
    for(int i=1;i<=n;i++)
	aux[i]=v[i].y;
    sort(aux+1,aux+n+1);
    for(int i=1;i<=n;i++)
	if(i==1 || aux[i]!=aux[i-1])
            H[(aux[i]>0?aux[i]:-aux[i])%hmod].push_back(make_pair(aux[i],++ind));
    for(int i=1;i<=n;i++)
    {
	int h=(v[i].y>0?v[i].y:-v[i].y)%hmod;
	for(vector< pair<int,int> >::iterator it=H[h].begin();it!=H[h].end();it++)
		if(it->first==v[i].y)
		{
			v[i].y=it->second;
			break;
		}
        ans=max(ans,v[i].y);
    }
    return ans;
}
char buf[7000000];int crs=0,sz=7000000;
inline 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,x1,x2,y1,y2;
    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(x1);
        getInt(y1);
        getInt(x2);
        getInt(y2);
        v[++N].x=x2;  v[N].y=y2;  v[N].type=1;v[N].ind=i;v[N].semn=true;
        v[++N].x=x2;  v[N].y=y1-1;v[N].type=1;v[N].ind=i;v[N].semn=false;
        v[++N].x=x1-1;v[N].y=y2;  v[N].type=1;v[N].ind=i;v[N].semn=false;
        v[++N].x=x1-1;v[N].y=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)
        {
        	for(int I=v[i].y;I<=MAX;I+=(I&(-I)))
			aib[I]++;
	}
	else
            ans[v[i].ind]+=(v[i].semn?1:-1)*query(v[i].y);
    for(int i=1;i<=m;i++)
        printf("%d\n",ans[i]);
    return 0;
}