Cod sursa(job #766305)

Utilizator vendettaSalajan Razvan vendetta Data 10 iulie 2012 22:23:28
Problema Zoo Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.22 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

#define nmax 16005
#define x first
#define y second

ifstream f("zoo.in");
ofstream g("zoo.out");

int n, m;
pair<int,int>  Y[nmax];
vector<int> aint[nmax*4];
int viz[nmax*4];
vector<int> X;
int sum = 0;

void citeste(){

    f >> n;

    for(int i=1; i<=n; i++){
        int x, y;
        f >> x >> y;
        X.push_back(x);
        Y[i]=make_pair(x,y);
    }

    sort(X.begin(), X.end() );
    sort(Y+1, Y+n+1);
}

void udpate(int nod, int st, int dr, int poz, int val){

    if (st == dr){
        viz[nod] = 1;
        aint[nod].push_back(val);
        return;
    }

    int mij = (st + dr) / 2;
    if (poz <= mij) udpate(nod*2, st, mij, poz, val);
               else udpate(nod*2+1, mij+1, dr, poz, val);

    if (viz[nod*2] == 1 && viz[nod*2+1] == 1){
            for(int i=0; i<aint[nod*2].size(); i++) aint[nod].push_back(aint[nod*2][i]);
            for(int i=0; i<aint[nod*2+1].size(); i++) aint[nod].push_back(aint[nod*2+1][i]);
            viz[nod] = 1;
            sort(aint[nod].begin(), aint[nod].end() );
    }

}

void query(int nod, int st, int dr, int a, int b, int y1, int y2){

    if (a <= st && dr <= b){
        int poz1 = lower_bound(aint[nod].begin(), aint[nod].end(), y1)-aint[nod].begin();
        int poz2 = upper_bound(aint[nod].begin(), aint[nod].end(), y2)-aint[nod].begin();
        sum += (poz2-poz1);
        return;
    }

    int mij = (st + dr)/2;
    if (a <= mij) query(nod*2, st, mij, a, b, y1, y2);
    if (b > mij) query(nod*2+1, mij+1, dr, a, b, y1, y2);

}


void rezolva(){

    f >> m;

    for(int i=1; i<=n; i++){
        udpate(1,1,n,i,Y[i].y);
    }

    for(int i=1; i<=m; i++){
        int x1, y1, x2, y2;
        f >> x1 >> y1 >> x2 >> y2;
        if (y1 > y2) swap(y1,y2);
        int poz1 = lower_bound(X.begin(), X.end(), x1)-X.begin();
        int poz2 = upper_bound(X.begin(), X.end(), x2)-X.begin()-1;
        poz1++, poz2++;
        sum = 0;
        query(1,1,n, poz1, poz2, y1, y2);
        g << sum << "\n";
    }

}

int main(){

    citeste();
    rezolva();

    f.close();
    g.close();

}