Cod sursa(job #2670157)

Utilizator PatrickCplusplusPatrick Kristian Ondreovici PatrickCplusplus Data 9 noiembrie 2020 10:33:18
Problema Zoo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.56 kb
#include <bits/stdc++.h>

using namespace std;

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

const int nmax = 16000;
int n, m, z = 1;
struct point{
    int x, y;
}v[nmax + 5];
vector <int> aint[nmax * 5 + 5], aux[nmax + 5], aux1, aux2;

bool cmp(point a, point b){
    if (a.x == b.x){
        return a.y < b.y;
    }
    return a.x < b.x;
}

vector <int> Merge(vector <int> a, vector <int> b){
    vector <int> c;
    int i = 0, j = 0;
    while (i < a.size() && j < b.size()){
        if (a[i] < b[j]){
            c.push_back(a[i++]);
        }
        else{
            c.push_back(b[j++]);
        }
    }
    while (i < a.size()){
        c.push_back(a[i++]);
    }
    while (j < b.size()){
        c.push_back(b[j++]);
    }
    return c;
}

void Build(int nod, int st, int dr){
    if (st > dr)
        return;
    if (st == dr){
        aint[nod] = aux[st];
        return;
    }
    int mid = (st + dr) / 2;
    Build(nod * 2, st, mid);
    Build(nod * 2 + 1, mid + 1, dr);
    aint[nod] = Merge(aint[nod * 2], aint[nod * 2 + 1]);
}

int Query(int nod, int st, int dr, int x1, int x2, int y1, int y2){
    if (st > dr){
        return 0;
    }
    if (st >= x1 && dr <= x2){
        return upper_bound(aint[nod].begin(), aint[nod].end(), y2) - lower_bound(aint[nod].begin(), aint[nod].end(), y1);
    }
    if (st > x2 || dr < x1){
        return 0;
    }
    int mid = (st + dr) / 2;
    return Query(nod * 2, st, mid, x1, x2, y1, y2) + Query(nod * 2 + 1, mid + 1, dr, x1, x2, y1, y2);
}

int main(){
    fin >> n;
    for (int i = 1; i <= n; ++i){
        fin >> v[i].x >> v[i].y;
    }
    sort(v + 1, v + n + 1, cmp);
    aux[1].push_back(v[1].y);
    aux1.push_back(v[1].x);
    aux2.push_back(1);
    for (int i = 2; i <= n; ++i){
        if (v[i].x != v[i - 1].x){
            ++z;
        }
        aux[z].push_back(v[i].y);
        aux1.push_back(v[i].x);
        aux2.push_back(z);
    }
    Build(1, 1, z);
    fin >> m;
    for (int i = 1; i <= m; ++i){
        int a, b, c, d;
        fin >> a >> b >> c >> d;
        c = (int)(upper_bound(aux1.begin(), aux1.end(), c) - aux1.begin());
        if (c == 0){
            fout << 0 << "\n";
            continue;
        }
        c = aux2[c - 1];
        a = (int)(lower_bound(aux1.begin(), aux1.end(), a) - aux1.begin());
        a = aux2[a];
        if (a > c){
            fout << 0 << "\n";
            continue;
        }
        fout << Query(1, 1, z, a, c, b, d) << "\n";
    }
    fin.close();
    fout.close();
    return 0;
}