Cod sursa(job #3138847)

Utilizator DariusM17Murgoci Darius DariusM17 Data 22 iunie 2023 21:28:57
Problema Zoo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.37 kb
//#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
#include <unordered_map> 
#include <map>
#include <set>
#include <unordered_set>
#include <bitset>
#include <cstring>
using namespace std;
string file = "zoo";
ifstream cin(file + ".in");
ofstream cout(file + ".out");
#define FAST ios_base::sync_with_stdio(0), cin.tie(0),cout.tie(0) ;
const int NMAX = 16005;
int n, q;
vector <pair<int, int>> c;
vector <int> v[NMAX], aint[4*NMAX];
vector <int> normal;
void norm(void) {
    for (int i = 0; i < n; ++i) normal.push_back(c[i].first);
    sort(normal.begin(), normal.end());
    normal.resize(unique(normal.begin(), normal.end()) - normal.begin());
    for (int i = 0; i < n; ++i) {
        int aux = lower_bound(normal.begin(), normal.end(), c[i].first) - normal.begin() + 1;
        v[aux].push_back(c[i].second);
    }
}
void build(int nod, int st, int dr) {
    if (st == dr) {
        swap(aint[nod], v[st]);
        sort(aint[nod].begin(), aint[nod].end());
        return;
    }
    int mij = (st + dr) >> 1;
    build(2 * nod, st, mij);
    build(2 * nod + 1, mij + 1, dr);
    merge(aint[2 * nod + 1].begin(), aint[2 * nod + 1].end(), aint[2 * nod].begin(), aint[2 * nod].end(), back_inserter(aint[nod]));
}
int query(int nod, int st, int dr, int xi, int yi, int xf, int yf) {
    if (st >= xi && dr <= xf) return upper_bound(aint[nod].begin(), aint[nod].end(), yf) - lower_bound(aint[nod].begin(), aint[nod].end(), yi) ;
    int mij = (st + dr) >> 1, ans1 = 0, ans2 = 0;
    if (xf <= mij) return query(2 * nod, st, mij, xi, yi, xf, yf);
    if (xi >= mij + 1) return query(2 * nod + 1, mij + 1, dr, xi, yi, xf, yf);
    ans1 = query(2 * nod, st, mij, xi, yi, xf, yf), ans2 = query(2 * nod + 1, mij + 1, dr, xi, yi, xf, yf);
    return ans1 + ans2;
    
}
int main(void)
{
    cin >> n;
    for (int i = 1, x, y; i <= n; ++i) cin >> x >> y, c.push_back({ x,y });
    norm();
    build(1, 1, normal.size());
    cin >> q;
    for (int i = 1, xi, yi, xf, yf; i <= q; ++i) {
        cin >> xi >> yi >> xf >> yf;
        xi = lower_bound(normal.begin(), normal.end(), xi) - normal.begin() + 1;
        xf = upper_bound(normal.begin(), normal.end(), xf) - normal.begin();
        if (xi > xf) cout << 0 << '\n';
        else cout << query(1, 1, normal.size(), xi, yi, xf, yf) << '\n';
    }
    return 0;
}