Cod sursa(job #2578935)

Utilizator smoc_georgemarianSmoc George-Marian smoc_georgemarian Data 11 martie 2020 18:57:26
Problema Zoo Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.02 kb
#include <bits/stdc++.h>
#define NMAX 16009
using namespace std;
ifstream fin("zoo.in");
ofstream fout("zoo.out");
vector<int> a[4*NMAX];
pair<int,int> v[NMAX];
int n,m,i;
void citire();
void build(int node, int st, int dr);

int query(int node, int st, int dr, int x, int y, int valmin, int valmax);
int cautbin();

int x1,x2,ys,yd;
int cautbin1();
int main()
{citire();
 build(1,1,n);
 fin>>m;
 for(i=1;i<=m;i++)
    {
     fin>>x1>>ys>>x2>>yd;
     int st=cautbin();
     int dr=cautbin1();
     fout<< query(1,1,n,st,dr,ys,yd)<<'\n';
    }
    return 0;
}
void citire()
{int x,y;
 int i;

  fin>>n;
  for(i=1;i<=n;i++)
    {fin>>x>>y;
     v[i]={x,y};
    }
  sort(v+1,v+n+1);
}
void build(int node, int st, int dr)
{
  int mj=(dr+st)/2;
  if(dr==st)
    {
     a[node].push_back(v[st].second);
     return;
    }
  build(2*node, st,mj);
  build(2*node+1, mj+1,dr);

  a[node].resize(a[2 * node].size() + a[2 * node + 1].size());

  merge(a[2 * node].begin(), a[2 * node].end(),a[2 * node + 1].begin(), a[2 * node + 1].end(),a[node].begin());
}
int cautbin()
{
 int st,dr,mj;
 st=0;
 dr=n+1;
 while(dr-st>1)
        {
         mj=(dr+st)/2;
         if(v[mj].first<x1)
             st=mj;
             else
                dr=mj;
        }
  return st+1;
}
int cautbin1()
{
 int st,dr,mj;
 st=0;
 dr=n+1;
 while(dr-st>1)
        {
         mj=(dr+st)/2;
         if(v[mj].first>x2)
             dr=mj;
             else
                st=mj;
        }
  return dr-1;
}
int query(int node, int st, int dr, int x, int y, int valmin, int valmax)
{vector<int>::iterator p,q;
  if( x<=st && dr<=y   )
    {
      p= lower_bound( a[node].begin(), a[node].end(),valmin );

      q= upper_bound( a[node].begin(), a[node].end(),valmax );
     return q-p;
    }
   int mj=(dr+st)/2;
   int ans1=0;
   int ans2=0;
   if( x<=mj )
       ans1= query(2*node,st,mj,x,y,valmin,valmax);

   if( y>mj )
       ans2= query(2*node+1,mj+1,dr,x,y,valmin,valmax);
   return ans1+ans2;
}