Cod sursa(job #1154115)

Utilizator omerOmer Cerrahoglu omer Data 25 martie 2014 23:09:40
Problema Zoo Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.86 kb
#include<stdio.h>
#include<algorithm>
#include<vector>
const int M=100001, N=16001;
using namespace std;
FILE *f,*g;

int x[2][N], xy[2][N];  int n,nr[2];

vector<int> valori[N];                             //doar vactorul valori va fi folosit, restul sunt yedek

struct nod{

    int y,rasp;
    bool ok;
};

vector<nod> forquery[N]; int m;

int aib[N], intrb[M];

void read(void){

    f=fopen("zoo.in","r");
    g=fopen("zoo.out","w");

    fscanf(f,"%d",&n);

    int i;
    for(i=1;i<=n;i++) fscanf(f,"%d%d",&xy[0][i],&xy[1][i]);
}

void sortare(void){

    int i;
    for(i=1; i<=n; i++) {x[0][i]=xy[0][i]; x[1][i]=xy[1][i]; }

    sort(x[0]+1, x[0]+n+1);
    sort(x[1]+1, x[1]+n+1);

    int i1,i2;
    i1=1;  
    for(i2=2;i2<=n;i2++){
        
        if (x[0][i2] != x[0][i1]) x[0][++i1]=x[0][i2];
        
    }
    nr[0]=i1;
    
    i1=1; 
    for(i2=2;i2<=n;i2++)
        if (x[1][i2] != x[1][i1]) x[1][++i1]=x[1][i2];
        
    nr[1]=i1;

   

}

int binsearch(int a, int b){

    if (a<x[b][1]) return 0;
    else if (a>=x[b][nr[b]]) return nr[b];
        else {
            
            int l=1, r=nr[b], mid;

            while(r-l>1){
                
                mid=(l+r)/2;
                if (a < x[b][mid]) r=mid;
                else l=mid;
            }

            return l;
        }
}

void makegraph(void){

    int i;
    for(i=1;i<=n;i++) valori[binsearch(xy[0][i],0)].push_back(binsearch(xy[1][i],1));
}

void preambulquery(void){

    fscanf(f,"%d",&m);

    int i; int a,b,c,d; nod dumm;
    for(i=1;i<=m;i++){

        fscanf(f,"%d%d%d%d",&a,&b,&c,&d);
        
        int ay=binsearch(a-1,0), cy=binsearch(c,0);
        dumm.y=binsearch(b-1,1); dumm.rasp=i; dumm.ok=1;
        forquery[ay].push_back(dumm);
        dumm.ok=0;
        forquery[cy].push_back(dumm);
        dumm.y=binsearch(d,1);
        forquery[ay].push_back(dumm);
        dumm.ok=1;
        forquery[cy].push_back(dumm);
    }
}

int suc(int l){

    return 2*l-(l&(l-1));
}

int pred(int l){

    return l&(l-1);
}

void update(int l){

    while (l <= nr[0]) {aib[l]++; l=suc(l); }
}

int query(int l){

    int sum=0;
    if (l) 
       while (l){
           sum+=aib[l];
           l=pred(l);
       }
    return sum;
        
}

void initline(int i){

    vector<int>::iterator it=valori[i].begin();

    while(it!=valori[i].end()){

        update(*it);
        it++;
    }

}

void solveline(int i){

    vector<nod>::iterator it=forquery[i].begin();

    while (it != forquery[i].end() ){

        if (it->ok) intrb[it->rasp] += query(it->y);
            else intrb[it->rasp] -= query(it->y);

        ++it;
    }
}

void solveall(void){

    int i;

    for(i=1; i<=nr[0]; i++) {initline(i); solveline(i); }

    for(i=1; i<=m ;i++) fprintf(g,"%d\n",intrb[i]);
}





int main(void){
    
    read(); 
    sortare(); 
    makegraph(); 
    preambulquery();
    solveall();
   
    
 
    return 0;
}