Cod sursa(job #1686508)

Utilizator sucureiSucureiRobert sucurei Data 12 aprilie 2016 12:01:11
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.49 kb
#include <cstdio>
#include <algorithm>
#include <cctype>
#define MAXN 16000
#define MAXM 100000
#define BUF_SIZE 4096
int pos=BUF_SIZE, poz=0;
char buf[BUF_SIZE], scrib[BUF_SIZE];
FILE *fin, *fout;
typedef struct{
    int x, y;
}mycreation;
mycreation v[MAXN];
int igrec[MAXN], aib[MAXN+1], val[MAXN+1], next[MAXN+1], lista[MAXN], st[2*MAXM+1], dr[2*MAXM+1], coef[2*MAXM+1], cine[2*MAXM+1], urm[2*MAXM+1];
int n, k, q, list[MAXN+1], cat[MAXN+1], ans[MAXM];
inline char nextch(){
    if(pos==BUF_SIZE){
        fread(buf, BUF_SIZE, 1, fin);
        pos=0;
    }
    return buf[pos++];
}
inline int read(){
    int x=0, semn=1;
    char ch=nextch();
    while((!isdigit(ch))&&(ch!='-')){
        ch=nextch();
    }
    if(ch=='-'){
        semn=-1;
        ch=nextch();
    }
    while(isdigit(ch)){
        x=10*x+ch-'0';
        ch=nextch();
    }
    return x*semn;
}
inline void putch(char ch){
    scrib[poz++]=ch;
    if(poz==BUF_SIZE){
        fwrite(scrib, 1, BUF_SIZE, fout);
        poz=0;
    }
}
inline void baga(int x){
    int cif[6];
    cif[0]=0;
    do{
        cif[++cif[0]]=x%10;
        x/=10;
    }while(x);
    while(cif[0]){
        putch(cif[cif[0]]+'0');
        cif[0]--;
    }
}
bool cmp(const mycreation a, const mycreation b){
    return a.x<b.x;
}
inline void add(int x, int y){
    val[++k]=y;
    next[k]=lista[x];
    lista[x]=k;
}
inline void adauga(int x, int y1, int y2, int t, int u){
    st[++q]=y1;
    dr[q]=y2;
    coef[q]=t;
    cine[q]=u;
    urm[q]=list[x];
    list[x]=q;
}
inline int norm(int y){
    int rez=-1;
    for(int pas=1<<13; pas; pas>>=1){
        if((rez+pas<n)&&(igrec[rez+pas]<=y)){
            rez+=pas;
        }
    }
    return rez+1;
}
inline void update(int p){
    while(p<=n){
        aib[p]++;
        p+=p&(-p);
    }
}
inline int query(int p){
    int s=0;
    while(p>0){
        s+=aib[p];
        p-=p&(-p);
    }
    return s;
}
int main(){
    int i, a, j, rez, pas, m, x1, y1, x2, y2, p;
    fin=fopen("zoo.in", "r");
    fout=fopen("zoo.out", "w");
    n=read();
    for(i=0; i<n; i++){
        v[i].x=read();
        v[i].y=read();
        igrec[i]=v[i].y;
    }
    std::sort(v, v+n, cmp);
    std::sort(igrec, igrec+n);
    a=0;
    i=0;
    while(i<n){
        j=i;
        if((j<n)&&(v[i].x==v[j].x)){
            cat[i]=a;
            add(a, norm(v[j].y));
            j++;
        }
        i=j;
        a++;
    }
    m=read();
    for(i=0; i<m; i++){
        x1=read();
        y1=norm(read()-1);
        x2=read();
        y2=norm(read());
        rez=-1;
        for(pas=1<<13; pas; pas>>=1){
            if((rez+pas<n)&&(v[rez+pas].x<x1)){
                rez+=pas;
            }
        }
        if(rez!=-1){
            adauga(cat[rez], y1, y2, -1, i);
        }
        rez=-1;
        for(pas=1<<13; pas; pas>>=1){
            if((rez+pas<n)&&(v[rez+pas].x<=x2)){
                rez+=pas;
            }
        }
        if(rez!=-1){
            adauga(cat[rez], y1, y2, 1, i);
        }
    }
    for(i=0; i<a; i++){
        p=lista[i];
        while(p){
            update(val[p]);
            p=next[p];
        }
        p=list[i];
        while(p){
            ans[cine[p]]+=coef[p]*(query(dr[p])-query(st[p]));
            p=urm[p];
        }
    }
    for(i=0; i<m; i++){
        baga(ans[i]);
        putch('\n');
    }
    fwrite(scrib, 1, poz, fout);
    fclose(fin);
    fclose(fout);
    return 0;
}