Cod sursa(job #2988822)

Utilizator Luca529Taschina Luca Luca529 Data 5 martie 2023 15:34:39
Problema Zoo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.05 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;
ifstream fin("zoo.in");
ofstream fout("zoo.out");
struct Data{
int i, j;
}y[20001];

vector<int> x[100001];

void QS(int st, int dr)
{if(st<dr)
 {int mij=(st+dr)/2, i=st, j=dr, d=0;
  swap(y[st], y[mij]);
  while(i<j)
  {if(y[i].i>y[j].i || (y[i].i==y[j].i && y[i].j>y[j].j))swap(y[i], y[j]), d=1-d;
   i+=d;
   j-=1-d;
  }
  QS(st, i-1);
  QS(i+1, dr);
 }
}

void Build(int nod, int st, int dr)
{if(st==dr)
 x[nod].push_back(y[st].j);
 else
 {int mij=(st+dr)/2;

  Build(nod*2, st, mij);
  Build(nod*2+1, mij+1, dr);

  int i=0, j=0;
  while(i<x[nod*2].size() && j<x[nod*2+1].size())
  if(x[nod*2][i]<x[nod*2+1][j])x[nod].push_back(x[nod*2][i]), i++;
  else x[nod].push_back(x[nod*2+1][j]), j++;

  while(i<x[nod*2].size())
  {x[nod].push_back(x[nod*2][i]);
   i++;
  }

  while(j<x[nod*2+1].size())
  {x[nod].push_back(x[nod*2+1][j]);
   j++;
  }
 }
}

int Query(int nod, int st, int dr, int a, int b, int c, int d)
{if(st<=dr)
 {if(a<=y[st].i && y[dr].i<=c)
  {int p1, p2;
   p1=lower_bound(x[nod].begin(), x[nod].end(), b)-x[nod].begin();
   p2=upper_bound(x[nod].begin(), x[nod].end(), d)-x[nod].begin();

   return p2-p1;
  }
  else if(st!=dr && y[st].i<=c && y[dr].i>=a)
  {int mij=(st+dr)/2;

   if(y[mij].i==c)
   {int a1=Query(nod*2, st, mij, a, b, c, d), b1=Query(nod*2+1, mij+1, dr, a, b, c, d);
    return a1+b1;
   }

   if(y[mij].i>=c)return Query(nod*2, st, mij, a, b, c, d);
   if(y[mij].i<a)return Query(nod*2+1, mij+1, dr, a, b, c, d);

   int a1=Query(nod*2, st, mij, a, b, c, d), b1=Query(nod*2+1, mij+1, dr, a, b, c, d);
   return a1+b1;
  }
 }
 return 0;
}

int main()
{   int n, m, a, b, c, d;
    fin>>n;
    for(int i=1;i<=n;i++)
    fin>>y[i].i>>y[i].j;

    QS(1, n);
    Build(1, 1, n);

    fin>>m;
    for(int i=1;i<=m;i++)
    {fin>>a>>b>>c>>d;
     if(c<a)swap(a, c);
     if(d<b)swap(d, b);

     fout<<Query(1, 1, n, a, b, c, d)<<"\n";
    }

    return 0;
}