Cod sursa(job #766735)

Utilizator vendettaSalajan Razvan vendetta Data 12 iulie 2012 00:17:25
Problema Zoo Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.35 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);
        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);

    aint[nod].resize(aint[nod*2].size() + aint[nod*2+1].size());
    merge(aint[nod*2].begin(), aint[nod*2].end(), aint[nod*2+1].begin(), aint[nod*2+1].end(), aint[nod].begin());

}
*/
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 build(int nod, int st, int dr){

    if (st == dr){
        aint[nod].push_back(a[st].y);
        return;
    }
    int mij = (st +dr) / 2;
    build(nod*2, st, mij);
    build(nod*2+1, mij+1, dr);

    aint[nod].resize(aint[nod*2].size() + aint[nod*2+1].size());
    merge(aint[nod*2].begin(), aint[nod*2].end(), aint[nod*2+1].begin(), aint[nod*2+1].end(), aint[nod].begin());

}

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
    }
*/
    build(1,1,n);
    f >> m;
    for(int i=1; i<=m; i++){
        int x1, y1, x2, y2;
        f >> x1 >> y1 >> x2 >> 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();

}