Cod sursa(job #3264510)

Utilizator BOSSSTEFANPetrescu Ioan Stefan BOSSSTEFAN Data 21 decembrie 2024 20:45:27
Problema Zoo Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.41 kb
#include <bits/stdc++.h>
#define inf INT_MAX
using namespace std;
const int nmax = 16000;
struct ura
{
    int a, b;
}v[nmax + 1];
int l[nmax + 1], c[nmax + 1];
bool cmp1(ura a, ura b)
{
    return a.a < b.a;
}
bool cmp2(ura a, ura b)
{
    return a.b < b.b;
}
int cbd(int v[], int n, int val)
{
    int st = 1, dr = n, poz = -1, mij;
    while(st <= dr)
    {
        mij = (st + dr) / 2;
        if(val <= v[mij])
        {
            poz = mij;
            dr = mij - 1;
        }
        else
            st = mij + 1;
    }
    return poz;
}
int cbs(int v[], int n, int val)
{
    int st = 1, dr = n, poz = -1, mij;
    while(st <= dr)
    {
        mij = (st + dr) / 2;
        if(v[mij] <= val)
        {
            poz = mij;
            st = mij + 1;
        }
        else
            dr = mij - 1;
    }
    return poz;
}
class SegmentTree
{
private :
    int n;
    vector <vector <int>> seg;
    void update(int nod, int st, int dr, int poz, int val)
    {
        seg[nod].push_back(val);
        if(st==dr)
            return;
        int mij = (st + dr) / 2;
        if(poz <= mij)
            update(nod * 2, st, mij, poz, val);
        else
            update(nod * 2 + 1, mij + 1, dr, poz, val);
    }
    void query(int nod, int st, int dr, int a, int b, int c, int d, int &ans)
    {
        if(a <= st && dr <= b)
        {
            int i, j;
            for(i = 0; i < seg[nod].size() && seg[nod][i] < c; i++);
            for(j = seg[nod].size() - 1; j > 0 && seg[nod][j] > d; j--);
            ans += j - i + 1;
            return;
        }
        int mij = (st + dr) / 2;
        if(a <= mij)
            query(nod * 2, st, mij, a, b, c, d, ans);
        if(b > mij)
            query(nod * 2 + 1, mij + 1, dr, a, b, c, d, ans);
    }
public :
    SegmentTree(int N)
    {
        n = N;
        seg.resize(1 + N * 4);
    }
    void upd(int a, int b)
    {
        update(1, 1, n, a, b);
    }
    int qry(int a, int b, int c, int d)
    {
        if(a == -1 || b == -1 || c == -1 || d == -1)
            return 0;
        if(a > b || c > d)
            return 0;
        int ans = 0;
        query(1, 1, n, a, b, c, d, ans);
        return ans;
    }
};
int main()
{
    freopen("zoo.in", "r", stdin);
    freopen("zoo.out", "w", stdout);
    ios :: sync_with_stdio(false);
    cin.tie(0);
    int n,i;
    for(i = 0; i <= n; i++)
        l[i] = c[i] = inf;
    cin >> n;
    for(i = 1; i <= n; i++)
    {
        cin >> v[i].a >> v[i].b;
    }
    sort(v + 1, v + n + 1, cmp1);
    for(i = 1; i <= n; i++)
    {
        if(v[i].a != l[v[i - 1].a])
        {
            l[v[i - 1].a + 1] = v[i].a;
            v[i].a = v[i - 1].a + 1;
        }
        else
            v[i].a = v[i - 1].a;
    }
    SegmentTree ab(v[n].a);
    sort(v + 1, v + n + 1, cmp2);
    for(i = 1; i <= n; i++)
    {
        if(v[i].b != c[v[i - 1].b])
        {
            c[v[i - 1].b + 1] = v[i].b;
            v[i].b = v[i - 1].b + 1;
        }
        else
            v[i].b = v[i - 1].b;
        ab.upd(v[i].a, v[i].b);
    }
    int q, x1, x2, y1, y2;
    cin >> q;
    while(q > 0)
    {
        q--;
        cin >> x1 >> y1 >> x2 >> y2;
        x1 = cbd(l, n, x1);
        x2 = cbs(l, n, x2);
        y1 = cbd(c, n, y1);
        y2 = cbs(c, n, y2);
        cout << ab.qry(x1, x2, y1, y2) << '\n';
    }
    return 0;
}