Cod sursa(job #2827338)

Utilizator ElizaTElla Rose ElizaT Data 5 ianuarie 2022 17:08:42
Problema Zoo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.42 kb
#include <bits/stdc++.h>

using namespace std;

const int NMAX = 16e3;
struct pct {
    int x,y;
    bool operator<(const pct& p) const {
        return x < p.x;
    }
}v[NMAX + 5],p1,p2;
vector<int> aib[NMAX + 5];
int n;

int calc(int a) {
    return (a ^ (a & (a - 1)));
}
void update(int poz, int val) {
    while (poz <= n) {
        aib[poz].push_back(val);
        poz += calc(poz);
    }
}
int query(int poz, int inc, int sf) {
    int ans = 0,a,b;
    while (poz > 0) {
        a = lower_bound(aib[poz].begin(), aib[poz].end(), inc) - aib[poz].begin();
        b = upper_bound(aib[poz].begin(), aib[poz].end(), sf) - aib[poz].begin();
        ans += b - a;
        poz -= calc(poz);
    }
    return ans;
}
int main()
{
    ifstream fin("zoo.in");
    ofstream fout("zoo.out");
    int m,a,b;
    fin >> n;
    for (int i = 1;i <= n;i++)
        fin >> v[i].x >> v[i].y;
    sort(v + 1, v + 1 + n);
    for (int i = 1;i <= n;i++)
        update(i, v[i].y);
    for (int i = 1;i <= n;i++)
        sort(aib[i].begin(), aib[i].end());
    fin >> m;
    for (int i = 0;i < m;i++) {
        fin >> p1.x >> p1.y >> p2.x >> p2.y;
        a = lower_bound(v + 1, v + n + 1, p1) - v;
        b = upper_bound(v + 1, v + n + 1, p2) - v;
        if (a > 0)
            a--;
        if (b > 0)
            b--;
        fout << query(b, p1.y, p2.y) - query(a, p1.y, p2.y) << '\n';
    }
    return 0;
}