Cod sursa(job #2961348)

Utilizator Luca529Taschina Luca Luca529 Data 6 ianuarie 2023 11:51:45
Problema Zoo Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.89 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[20000];
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[mij], y[st]);
  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+1][j]), j++;
  else x[nod].push_back(x[nod*2][i]), i++;

  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(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
 {int mij=(y[st].i+y[dr].i)/2, m=(st+dr)/2;

  if(mij>=c)return Query(nod*2, st, m, a, b, c, d);
  else if(mij<a)return Query(nod*2+1, m+1, dr, a, b, c, d);

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

  return a1+b1;
 }
}

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);
/*
    for(int i=1;i<=n*3;i++, cout<<endl)
    for(int j=0;j<x[i].size();j++)
    cout<<x[i][j]<<" ";
*/
    fin>>m;
    for(int i=1;i<=m;i++)
    {fin>>a>>b>>c>>d;
     fout<<Query(1, 1, n, a, b, c, d)<<"\n";
    }

    return 0;
}