Cod sursa(job #2988738)

Utilizator Luca529Taschina Luca Luca529 Data 5 martie 2023 13:51:12
Problema Zoo Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.11 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>

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

vector<long long int> x[100001];

void QS(int st, int dr)
{if(st<dr)
 {long long 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(long long int nod, long long int st, long long int dr)
{if(st==dr)
 x[nod].push_back(y[st].j);
 else
 {long long int mij=(st+dr)/2;

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

  long long 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++;
  }
 }
}

long long int Query(long long int nod, long long int st, long long int dr, long long int a, long long int b, long long int c, long long int d)
{if(st<=dr)
 {if(a<=y[st].i && y[dr].i<=c)
  {long long 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)
  {long long int mij=(st+dr)/2;

   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);

   long long 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()
{   long long 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;
}