Cod sursa(job #1777062)

Utilizator PopoviciRobertPopovici Robert PopoviciRobert Data 12 octombrie 2016 00:26:53
Problema Zoo Scor 100
Compilator cpp Status done
Runda cerculdeinfo-lectia2-arborideintervale Marime 2.84 kb
#include <cstdio>
#include <cctype>
#define MAXBUF 1<<17
FILE*fi,*fout;
char buf[MAXBUF];
int pos=MAXBUF;
inline char nextch(){
    if(pos==MAXBUF){
        fread(buf,1,MAXBUF,fi);
        pos=0;
    }
    return buf[pos++];
}
inline int getnr(){
   char a=nextch();
   char sign=1;
   if(a=='-')
      sign=-1;
   while(isdigit(a)==0)
      a=nextch();
   int nr=0;
   while(isdigit(a)==1){
      nr=nr*10+a-'0';
      a=nextch();
   }
   return nr*sign;
}
#include <algorithm>
#include <cstring>
#include <vector>
#define MAXN 16000
#define MAXM 100000
#define INF 2000000001
struct Data{
   int val;
   int poz;
};
Data X[MAXN+2];
bool cmp(Data a,Data b){
    return a.val<b.val;
}
int Y[MAXN+1];
std::vector <int> aint[4*MAXN+1];
void update(int nod,int left,int right){
     int i,j,n1,n2;
     if(left==right)
        aint[nod].push_back(Y[X[left].poz]);
     else{
         int med=(left+right)/2;
         update(2*nod,left,med);
         update(2*nod+1,med+1,right);
         i=j=0;
         n1=aint[2*nod].size();
         n2=aint[2*nod+1].size();
         aint[nod].clear();
         while(i<n1&&j<n2){
             if(aint[2*nod][i]<aint[2*nod+1][j]){
                aint[nod].push_back(aint[2*nod][i]);
                i++;
             }
             else{
                aint[nod].push_back(aint[2*nod+1][j]);
                j++;
             }
         }
         while(i<n1){
            aint[nod].push_back(aint[2*nod][i]);
            i++;
         }
         while(j<n2){
            aint[nod].push_back(aint[2*nod+1][j]);
            j++;
         }
     }
}
int ans;
void query(int nod,int left,int right,int l,int r,int y1,int y2){
     int rez1,rez2;
     if(l<=left&&right<=r){
        rez1=lower_bound(aint[nod].begin(),aint[nod].end(),y1)-aint[nod].begin();
        rez2=upper_bound(aint[nod].begin(),aint[nod].end(),y2)-aint[nod].begin();
        ans+=rez2-rez1;
     }
     else{
        int med=(left+right)/2;
        if(l<=med)
          query(2*nod,left,med,l,r,y1,y2);
        if(med<r)
          query(2*nod+1,med+1,right,l,r,y1,y2);
     }
}
int main(){
   int i,j,n,m,x1,x2,y1,y2,rez1,rez2,pas,log;
   fi=fopen("zoo.in" ,"r");
   fout=fopen("zoo.out" ,"w");
   n=getnr();
   for(i=1;i<=n;i++){
      X[i].val=getnr();
      X[i].poz=i;
      Y[i]=getnr();
   }
   std::sort(X+1,X+n+1,cmp);
   update(1,1,n);
   log=0;
   while((1<<log)<=n)
     log++;
   log--;
   m=getnr();
   for(i=1;i<=m;i++){
      ans=0;
      x1=getnr();
      y1=getnr();
      x2=getnr();
      y2=getnr();
      rez1=rez2=0;
      for(pas=1<<log;pas;pas>>=1){
         if(rez1+pas<=n&&X[rez1+pas].val<x1)
            rez1+=pas;
         if(rez2+pas<=n&&X[rez2+pas].val<=x2)
            rez2+=pas;
      }
      rez1++;
      if(rez1>rez2)
        ans=0;
      else
        query(1,1,n,rez1,rez2,y1,y2);
      fprintf(fout,"%d\n" ,ans);
   }
   fclose(fi);
   fclose(fout);
   return 0;
}