Cod sursa(job #3261490)

Utilizator BOSSSTEFANPetrescu Ioan Stefan BOSSSTEFAN Data 6 decembrie 2024 13:20:44
Problema Zoo Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.84 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.b;
}
bool cmp2(ura a, ura b)
{
    return a.b < b.b;
}
int cbs(int v[], int n, int val)
{
    int st = 1, dr = n, poz, mij;
    while(st <= dr)
    {
        mij = (st + dr) / 2;
        if(v[mij] <= val)
        {
            poz = mij;
            dr = mij - 1;
        }
        else
            st = mij + 1;
    }
    return v[poz];
}
int cbd(int v[], int n, int val)
{
    int st = 1, dr = n, poz, mij;
    while(st <= dr)
    {
        mij = (st + dr) / 2;
        if(v[mij] >= val)
        {
            poz = mij;
            dr = mij - 1;
        }
        else
            st = mij + 1;
    }
    return v[poz];
}
int main()
{
    freopen("zoo.in", "r", stdin);
    freopen("zoo.out", "w", stdout);
    ios :: sync_with_stdio(false);
    cin.tie(0);
    int n,i;
    l[0] = inf;
    memset(l, inf, n);
    memset(c, inf, n);
    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;
        }
    }
    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;
        }
    }
    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);

    }
    return 0;
}