Cod sursa(job #1760167)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 20 septembrie 2016 13:55:43
Problema Zoo Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.13 kb
#include<fstream>
#include<algorithm>
#include<vector>

using namespace std;

ofstream fout( "zoo.out" );

class InputReader{
public:
    InputReader() {}
    InputReader(const char *name) {
        fin = fopen(name, "r");
        buffpos = Size - 1;
    }

    inline InputReader &operator >> (int &n) {
        char x = nextpos();
        while ((x < '0' || x > '9') && x != '-') x = nextpos();
        int semn = 1;
        if (x == '-') {
            semn = -1; x = nextpos();
        }
        n = 0;
        while (x >= '0' && x <= '9') {
            n = n * 10 + x - '0';
            x = nextpos();
        }
        n *= semn;
        return *this;
    }
private:
    static const int Size = (1 << 17);
    FILE *fin;
    int buffpos;
    char buff[ Size ];

    inline char nextpos() {
        ++ buffpos;
        if (buffpos == Size) {
            fread(buff, Size, 1, fin);
            buffpos = 0;
        }
        return buff[ buffpos ];
    }
} fin ("zoo.in");

const int nmax = 16000;
const int mmax = 1e5;
const int cate_val = 4 * mmax + nmax + 1;
int n, m, nrm;
int solutie[mmax + 1];

struct pct{
    int ind, x, y, semn;

    pct() {}
    pct (int _ind, int _x, int _y, int _semn) {
        ind = _ind, x = _x, y = _y, semn = _semn;
    }

    inline bool operator < (const pct &a) const {
        if (x != a.x) return (x < a.x);
        if (ind != a.ind) return (ind < a.ind);
        return (y < a.y);
    }
} q[4 * mmax + nmax + 1];

class Aib{
public:
    int aib[cate_val + 1];

    void update (int pos, int val) {
        for (int i = pos; i <= cate_val; i += lsb( i )) {
            aib[ i ] += val;
        }
    }
    inline int query (int pos) {
        int ans = 0;
        for (int i = pos; i > 0; i -= lsb( i )) {
            ans += aib[ i ];
        }
        return ans;
    }
private:
    inline int lsb (int x) {
        return x & -x;
    }
} aib;

int aux[4 * mmax + nmax + 1];

inline bool cmp(int x, int y) {
    return (q[ x ].y < q[ y ].y);
}
void prelucrare_date() {
    for (int i = 1; i <= nrm; ++ i) {
        aux[ i ] = i;
    }
    sort(aux + 1, aux + nrm + 1, cmp);
    int ind = 1;
    for (int i = 1; i <= nrm; ++ i) {
        int last = q[ aux[ i ] ].y;
        q[ aux[ i ] ].y = ind;
        if (i < nrm && q[ aux[i + 1] ].y != last) {
            ++ ind;
        }
    }
}
void rezolva() {
    sort(q + 1, q + nrm + 1);

    for (int i = 1; i <= nrm; ++ i) {
        if (q[ i ].ind == 0) {
            aib.update(q[ i ].y, 1);
        } else {
            solutie[ q[ i ].ind ] += q[ i ].semn * aib.query( q[ i ].y );
        }
    }
}
int main() {
    fin >> n;
    nrm = 0;
    for (int i = 1; i <= n; ++ i) {
        int x, y;
        fin >> x >> y;
        q[ ++ nrm ] = pct(0, x, y, 0);
    }
    fin >> m;
    for (int i = 1; i <= m; ++ i) {
        int x, y, xx, yy;
        fin >> x >> y >> xx >> yy;
        q[ ++ nrm ] = pct(i, xx, yy, 1);
        q[ ++ nrm ] = pct(i, xx, y - 1, -1);
        q[ ++ nrm ] = pct(i, x - 1, yy, -1);
        q[ ++ nrm ] = pct(i, x - 1, y - 1, 1);
    }
    prelucrare_date();
    rezolva();

    for (int i = 1; i <= m; ++ i) {
        fout << solutie[ i ] << "\n";
    }

    fout.close();
    return 0;
}