Cod sursa(job #766758)

Utilizator vendettaSalajan Razvan vendetta Data 12 iulie 2012 01:30:09
Problema Zoo Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.36 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

#define nmax 16005

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

struct camp{
    int x, y;
};

int n, m, rez, viz[nmax*4];
camp a[nmax];
vector<int> aint[nmax*4];
string s;
int poz;

struct cmp{
    bool operator () (const camp &_a, const camp &_b){
        return _a.x < _b.x;
    }
};

void citeste_buf(int &nr){

    nr = 0;
    for(; (s[poz]<'0' || s[poz]>'9')&&s[poz]!='-'; poz++);
    int semn = 1;
    if (s[poz] == '-') semn = -1, ++poz;
    for(; s[poz]>='0'&&s[poz]<='9'; poz++){
        nr = nr * 10 + (s[poz] - '0');
    }
    nr = nr * semn;
}

void citeste(){

    s.clear();
    poz = 0;
    getline(f,s);
    citeste_buf(n);
    for(int i=1; i<=n; i++){
        int x, y;
        x = 0; y= 0;
        s.clear();
        poz = 0;
        getline(f,s);
        citeste_buf(x);
        citeste_buf(y);
        a[i].x = x;
        a[i].y = y;
    }

    sort(a+1, a+n+1, cmp() );//ii de ajuns sa le sortez doar dupa x;

}

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

    if (st == dr){
        aint[nod].push_back(val);
        viz[nod] = 1;
        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){
        viz[nod] = 1;//am terminat si cu asta; nemaifacand actualizari ulterioare asupra vreunui nod, pot face asta
        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]);
        sort(aint[nod].begin(), aint[nod].end() );
    }

}

int cb_st(int val){

    int st = 0;
    int dr = n+1;
    while(dr-st>1){
        int mij = (st+dr)/2;
        if (a[mij].x >= val){
            dr = mij;
        }else st = mij;
    }

    return dr;

}

int cb_dr(int val){

    int st = 0;
    int dr = n+1;
    while(dr-st>1){
        int mij = (st+dr)/2;
        if (a[mij].x <= val){
            st = mij;
        }else dr = mij;
    }

    return st;

}

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

    if (a <= st && dr <= b){
        int _y1 = lower_bound(aint[nod].begin(), aint[nod].end(), y1)-aint[nod].begin();
        int _y2 = upper_bound(aint[nod].begin(), aint[nod].end(), y2)-aint[nod].begin();
        rez += (_y2 - _y1);
        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(){

    for(int i=1; i<=n; i++){
        udpate(1, 1, n, i, a[i].y);//pe pozitia i din vectorul sortat pun in arbore tot pe poz i valoarea y
    }

    s.clear();
    poz=0;
    getline(f,s);
    citeste_buf(m);
    for(int i=1; i<=m; i++){
        int x1=0, y1=0, x2=0, y2=0;
        s.clear();
        poz = 0;
        getline(f,s);
        citeste_buf(x1);
        citeste_buf(y1);
        citeste_buf(x2);
        citeste_buf(y2);

        int _x1 = cb_st(x1);
        int _x2 = cb_dr(x2);
        rez = 0;
        if (_x1 <= _x2) query(1,1,n, _x1, _x2, y1, y2);
        g << rez << "\n";
    }

}

int main(){

    citeste();
    rezolva();

}