Cod sursa(job #502847)

Utilizator vladiiIonescu Vlad vladii Data 20 noiembrie 2010 16:33:21
Problema Zoo Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.15 kb
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
#define maxn 16010
#define MKP make_pair
#define PB push_back
#define ff first
#define ss second

int N, M, sol;
int y1, y2, start, finish;
vector<int> Aux;
vector<int> X[maxn];

struct Points {
    int x, y;
} P[maxn];

struct Aint {
    vector<int> Y;
} A[maxn];

int cmp(Points a, Points b) {
    if(a.x != b.x) {
         return a.x < b.x;
    }
    return a.y < b.y;
}

int cbin1(int val) {
    int ls = 0, ld = Aux.size() - 1;
    while(ls <= ld) {
         int mij = (ls + ld) >> 1;
         if(Aux[mij] == val) {
              return mij;
         }
         else if(Aux[mij] < val) {
              ls = mij + 1;
         }
         else {
              ld = mij - 1;
         }
    }
}

int cbin2(int val) {
    int rez = 0, ls = 0, ld = Aux.size() - 1;
    while(ls <= ld) {
         int mij = (ls + ld) >> 1;
         if(val <= Aux[mij]) {
              rez = mij;
              ld = mij - 1;
         }
         else {
              ls = mij + 1;
         }
    }

    return rez + 1;
}

int cbin3(int val) {
    int rez = Aux.size() - 1, ls = 0, ld = Aux.size() - 1;
    while(ls <= ld) {
         int mij = (ls + ld) >> 1;
         if(Aux[mij] <= val) {
              rez = mij;
              ls = mij + 1;
         }
         else {
              ld = mij - 1;
         }
    }

    return rez + 1;
}

void build(int nod, int left, int right) {
    if(left == right) {
         for(int i=0; i<X[left].size(); i++) {
              A[nod].Y.PB( X[left][i] );
         }
         return;
    }

    int mij = (left + right) >> 1;
    build(2*nod, left, mij);
    build(2*nod+1, mij+1, right);

    //interclasez left cu right
    int ls = 0, ld = 0;
    while(ls < A[2*nod].Y.size() && ld < A[2*nod+1].Y.size()) {
         if(A[2*nod].Y[ls] <= A[2*nod+1].Y[ld]) {
              A[nod].Y.PB( A[2*nod].Y[ls] );
              ls++;
         }
         else {
              A[nod].Y.PB( A[2*nod+1].Y[ld] );
              ld++;
         }
    }
    if(ls < A[2*nod].Y.size()) {
         for(int i=ls; i<A[2*nod].Y.size(); i++) {
              A[nod].Y.PB( A[2*nod].Y[i] );
         }
    }
    else if(ld < A[2*nod+1].Y.size()) {
         for(int i=ld; i<A[2*nod+1].Y.size(); i++) {
              A[nod].Y.PB( A[2*nod+1].Y[i] );
         }
    }
}

void query(int nod, int left, int right) {
    if(start <= left && right <= finish) {
         //fac cautare binara si elimin elementele
         //cu y < y1 si y > y2
         int ls = 0, ld = A[nod].Y.size() - 1;
         int posj = -1;
         while(ls <= ld) {
              int mij = (ls + ld) >> 1;
              if(A[nod].Y[mij] < y1) {
                   posj = mij;
                   ls = mij + 1;
              }
              else {
                   ld = mij - 1;
              }
         }

         ls = 0, ld = A[nod].Y.size() - 1;
         int poss = A[nod].Y.size();
         while(ls <= ld) {
              int mij = (ls + ld) >> 1;
              if(A[nod].Y[mij] > y2) {
                   poss = mij;
                   ld = mij - 1;
              }
              else {
                   ls = mij + 1;
              }
         }

         int sz = A[nod].Y.size();
         sol += sz - (posj + 1) - (sz - poss);

         return;
    }

    int mij = (left + right) >> 1;
    if(start <= mij) query(2*nod, left, mij);
    if(mij < finish) query(2*nod+1, mij+1, right);
}

int main() {
    FILE *f1=fopen("zoo.in", "r"), *f2=fopen("zoo.out", "w");
    int i, p, q, x1, x2;

    fscanf(f1, "%d\n", &N);
    for(i=1; i<=N; i++) {
         fscanf(f1, "%d %d\n", &P[i].x, &P[i].y);
         Aux.PB( P[i].x );
    }

    sort(P+1, P+N+1, cmp);
    sort(Aux.begin(), Aux.end());
    Aux.resize(unique(Aux.begin(), Aux.end()) - Aux.begin());

    for(i=1; i<=N; i++) {
         P[i].x = cbin1( P[i].x ) + 1;
         X[ P[i].x ].PB( P[i].y );
    }

    build(1, 1, N);

    fscanf(f1, "%d\n", &M);
    for(i=1; i<=M; i++) {
         fscanf(f1, "%d %d %d %d\n", &x1, &y1, &x2, &y2);

         start = cbin2( x1 );
         finish = cbin3( x2 );

         sol = 0;
         query(1, 1, N);

         fprintf(f2, "%d\n", sol);
    }

    fclose(f1); fclose(f2);
    return 0;
}