Cod sursa(job #1769378)

Utilizator PopoviciRobertPopovici Robert PopoviciRobert Data 2 octombrie 2016 14:20:47
Problema Zoo Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.55 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
struct Data{
   int val;
   char tip;
   int poz;
};
Data X[MAXN+MAXM*2+1];
bool cmp(Data a,Data b){
    return a.val<b.val;
}
struct Punct{
   int x;
   int y;
};
Punct P[MAXN+1];
struct Drept{
   int x1;
   int y1;
   int x2;
   int y2;
};
Drept D[MAXM+1];
std::vector <int> aint[4*(MAXN+2*MAXM)+1];
int cop[MAXN+1];
void update(int nod,int left,int right,int x,int y){
     int i,j,n1,n2;
     if(left==right){
        n1=aint[nod].size();
        i=0;
        while(i<n1&&aint[nod][i]<y){
           cop[i]=aint[nod][i];
           i++;
        }
        j=i;
        cop[j]=y;
        j++;
        while(i<n1&&aint[nod][i]>=y){
           cop[j]=aint[nod][i];
           j++;
           i++;
        }
        for(i=0;i<n1;i++)
           aint[nod][i]=cop[i];
        aint[nod].push_back(cop[i]);
     }
     else{
         int med=(left+right)/2;
         if(x<=med)
           update(2*nod,left,med,x,y);
         else
           update(2*nod+1,med+1,right,x,y);
         i=j=0;
         n1=aint[2*nod].size();
         n2=aint[2*nod+1].size();
         aint[nod].clear();
         while(i<n1||j<n2){
             if(i==n1||(i<n1&&j<n2&&aint[2*nod][i]>aint[2*nod+1][j])){
                 aint[nod].push_back(aint[2*nod+1][j]);
                 j++;
             }
             else{
                 aint[nod].push_back(aint[2*nod][i]);
                 i++;
             }
         }
     }
}
int ans;
void query(int nod,int left,int right,int x1,int x2,int y1,int y2){
     int rez1,rez2,pas,n;
     if(x1<=left&&right<=x2){
        rez1=-1;
        n=aint[nod].size();
        for(pas=1<<13;pas;pas>>=1)
          if(rez1+pas<n&&aint[nod][rez1+pas]<y1)
            rez1+=pas;
        rez2=-1;
        for(pas=1<<13;pas;pas>>=1)
          if(rez2+pas<n&&aint[nod][rez2+pas]<=y2)
            rez2+=pas;
        ans+=rez2-rez1;
     }
     else{
        int med=(left+right)/2;
        if(x1<=med)
          query(2*nod,left,med,x1,x2,y1,y2);
        if(med<x2)
          query(2*nod+1,med+1,right,x1,x2,y1,y2);
     }
}
int main(){
   int i,j,n,m,p,val,maxx;
   fi=fopen("zoo.in" ,"r");
   fout=fopen("zoo.out" ,"w");
   n=getnr();
   for(i=1;i<=n;i++){
      X[i].val=getnr();
      X[i].tip=0;
      X[i].poz=i;
      P[i].y=getnr();
   }
   m=getnr();
   p=n;
   for(i=1;i<=m;i++){
      p++;
      X[p].val=getnr();
      X[p].tip=1;
      X[p].poz=i;
      D[i].y1=getnr();
      p++;
      X[p].val=getnr();
      X[p].tip=1;
      X[p].poz=-i;
      D[i].y2=getnr();
   }
   std::sort(X+1,X+p+1,cmp);
   i=1;
   val=1;
   while(i<=p){
      j=i;
      while(j<=p&&X[i].val==X[j].val){
         if(X[j].tip==0)
            P[X[j].poz].x=val;
         else
           if(X[j].poz>0)
             D[X[j].poz].x1=val;
           else
             D[-X[j].poz].x2=val;
         j++;
      }
      val++;
      i=j;
   }
   maxx=val-1;
   for(i=1;i<=n;i++)
      update(1,1,maxx,P[i].x,P[i].y);
   for(i=1;i<=m;i++){
      ans=0;
      query(1,1,maxx,D[i].x1,D[i].x2,D[i].y1,D[i].y2);
      fprintf(fout,"%d\n" ,ans);
   }
   fclose(fi);
   fclose(fout);
   return 0;
}