Cod sursa(job #3161978)

Utilizator mariusn01Marius Nicoli mariusn01 Data 28 octombrie 2023 11:03:40
Problema Zoo Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.06 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#define DIMN 16010
#define DIMM 100010
using namespace std;

struct drept{
    int x1;
    int y1;
    int x2;
    int y2;
};

pair<int, int> p[DIMN];
drept d[DIMM];
int n, m, i, sol, k;
int s[DIMM*5];

vector<int> A[5*DIMM];

void build(int nod, int st, int dr) {
    for (int i=st;i<=dr;i++) {
        A[nod].push_back(p[i].second);
    }
    sort(A[nod].begin(), A[nod].end());
    if (st < dr) {
        int mid = (st+dr)/2;
        build(2*nod, st, mid);
        build(2*nod+1, mid+1, dr);
    }
}

int cauta_primul (int x, int nod) {
    int st = 0;
    int dr = A[nod].size()-1;
    while (st <= dr) {
        int mid = (st+dr)/2;
        if (A[nod][mid] >= x)
            dr = mid-1;
        else
            st = mid+1;
    }
    return st;
}

int cauta_ultimul (int x, int nod) {
    int st = 0;
    int dr = A[nod].size()-1;
    while (st <= dr) {
        int mid = (st+dr)/2;
        if (A[nod][mid] <= x)
            st = mid+1;
        else
            dr = mid-1;
    }
    return dr;
}

int cauta(int x) {
    int st = 0;
    int dr = k-1;
    while (st <= dr) {
        int mid = (st + dr) / 2;
        if (s[mid] == x)
            return mid;
        else
            if (x < s[mid])
                dr = mid-1;
            else
                st = mid+1;
    }
}

void query(int nod, int st, int dr, int poz) {
    if(d[poz].x1 <= p[st].first && d[poz].x2 >=p[dr].first) {
        sol += (cauta_ultimul(d[poz].y2, nod) - cauta_primul(d[poz].y1, nod) + 1);
    } else {
        int mid = (st + dr) / 2;
        if (d[poz].x1 <= p[mid].first)
            query(2*nod, st, mid, poz);
        if (d[poz].x2 >= p[mid+1].first)
            query(2*nod+1, mid+1, dr, poz);
    }
}

int main () {
    ifstream fin ("zoo.in");
    ofstream fout("zoo.out");

    fin>>n;
    for (i=1;i<=n;i++) {
        fin>>p[i].first>>p[i].second;
        s[k++] = p[i].first;
        s[k++] = p[i].second;
    }
    fin>>m;
    for (i=1;i<=m;i++) {
        fin>>d[i].x1>>d[i].y1>>d[i].x2>>d[i].y2;
        s[k++] = d[i].x1;
        s[k++] = d[i].y1;
        s[k++] = d[i].x2;
        s[k++] = d[i].y2;
    }
    sort(s, s+k);
    int last = 0;
    for (i=1;i<k;i++) {
        if (s[i] != s[last]) {
            s[++last] = s[i];
        }
    }
    k = last+1;
    for (i=1;i<=n;i++) {
        p[i].first = cauta (p[i].first);
        p[i].second = cauta (p[i].second);
    }
    for (i=1;i<=m;i++) {
        d[i].x1 = cauta (d[i].x1);
        d[i].y1 = cauta (d[i].y1);
        d[i].x2 = cauta (d[i].x2);
        d[i].y2 = cauta (d[i].y2);
    }
/**
    for (i=1;i<=n;i++) {
        cout<<p[i].first<<" "<<p[i].second<<"\n";
    }
    for (i=1;i<=m;i++) {
        cout<<d[i].x1<<" "<<d[i].y1<<" "<<d[i].x2<<" "<<d[i].y2<<"\n";
    }
**/
    sort(p+1, p+n+1);
    build(1, 1, n);
    for (int i=1;i<=m;i++) {
        sol = 0;
        query(1, 1, n, i);
        fout<<sol<<"\n";
    }

    return 0;
}