Cod sursa(job #315966)

Utilizator Magnuscont cu nume gresit sau fals Magnus Data 17 mai 2009 19:24:30
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.01 kb
# include <cstdio>     
# include <vector>
# include <algorithm>

using namespace std;

# define FIN "zoo.in"
# define FOUT "zoo.out"
# define max 2000000000
# define pb push_back
# define f first
# define s second
# define MAXN 1 << 14
# define MAXK 1 << 15

int N,M,i,j,xi,yi,xf,yf,rez;
pair <int, int> P[MAXN];
vector <int> A[MAXK];

void Interclas(int nod,int st,int dr)
{
 int mij, m, n, rh, lf, i;
 lf = nod << 1; rh = lf | 1;
 A[lf].pb(max+1);
 A[rh].pb(max+1);
 mij = dr - st;
 n = m = 0;
 for (i = 0; i <= mij; ++i)
 if (A[lf][n] < A[rh][m]) A[nod].pb(A[lf][n++]);
 else A[nod].pb(A[rh][m++]);
}

void build(int nod, int st, int dr)
{
 int mij;
 if (st == dr) A[nod].pb(P[st].s);
 else
 {
  mij = (st + dr) >> 1;
  build(nod << 1,st,mij);
  build(nod << 1 | 1,mij+1,dr);
  Interclas(nod, st, dr);
 }
}

int LowSearch(int nod,int st,int dr,int val)
{
 int mij, sol = -1;
 while (st <= dr)
 {
  mij = (st + dr) >> 1;
  if (val <= A[nod][mij])
  {
   sol = mij;
   dr = mij - 1;
  }
  else st = mij + 1;
 }
 return sol;
}

int UpSearch(int nod,int st,int dr,int val)
{
 int mij, sol = -1;
 while (st <= dr)
 {
  mij = (st + dr) >> 1;
  if (val >= A[nod][mij])
  {
   sol = mij;
   st = mij + 1;
  }
  else dr = mij - 1;
 }
 return sol;
}

void query(int nod,int st,int dr)
{
 int mij, Lx, Ly;
 if (P[st].f >= xi && xf >= P[dr].f)
 {
  Ly = LowSearch(nod,0,dr-st,yi);
  Lx = UpSearch(nod,0,dr-st,yf);
  if (Ly != -1 && Lx != -1) rez += Lx - Ly + 1;
 }
 else
 if (st != dr)
 {
  mij = (st + dr) >> 1;
  if (xi <= P[mij].f) query(nod << 1,st,mij);
  if (P[mij+1].f <= xf) query(nod << 1 | 1,mij+1,dr);
 }
}

int main()
{
 freopen(FIN,"r",stdin);
 freopen(FOUT,"w",stdout);
 scanf("%d",&N);
 for (i = 0; i < N; ++i) scanf("%d%d",&P[i].f,&P[i].s);
 sort(P, P+N);
 build(1,0,N-1);
 scanf("%d",&M);
 for (i = 1; i <= M; ++i)
 {
  scanf("%d%d",&xi,&yi);
  scanf("%d%d",&xf,&yf);
  rez = 0;
  query(1,0,N-1);
  printf("%d\n",rez);
 }
 return 0;
}