Cod sursa(job #2962865)

Utilizator PHOSSESSEDProsie Radu-Teodor PHOSSESSED Data 9 ianuarie 2023 17:33:49
Problema Zoo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.73 kb
#include<fstream>
#include<vector>
#include<algorithm>
#define eb emplace_back
using namespace std;

#pragma GCC optimize("Ofast")

class InParser {
    vector<char> str;
    int ptr;
    ifstream fin;

    char getChar() {
        if (ptr == int(str.size())) {
            fin.read(str.data(), str.size());
            ptr = 0;
        }
        return str[ptr++];
    }

    template<class T>
    T getInt() {
        char chr = getChar();
        while (!isdigit(chr) && chr != '-')
            chr = getChar();
        int sgn = +1;
        if (chr == '-') {
            sgn = -1;
            chr = getChar();
        }
        T num = 0;
        while (isdigit(chr)) {
            num = num * 10 + chr - '0';
            chr = getChar();
        }
        return sgn * num;
    }

public:
    InParser(const char* name) : str(1e5), ptr(str.size()), fin(name) { }
    ~InParser() { fin.close(); }

    template<class T>
    friend InParser& operator>>(InParser& in, T& num) {
        num = in.getInt<T>();
        return in;
    }
};

class OutParser {
    vector<char> str;
    int ptr;
    ofstream fout;

    void putChar(char chr) {
        if (ptr == int(str.size())) {
            fout.write(str.data(), str.size());
            ptr = 0;
        }
        str[ptr++] = chr;
    }

    template<class T>
    void putInt(T num) {
        if (num < 0) {
            putChar('-');
            num *= -1;
        }
        if (num > 9)
            putInt(num / 10);
        putChar(num % 10 + '0');
    }

public:
    OutParser(const char* name) : str(1e5), ptr(0), fout(name) { }
    ~OutParser() { fout.write(str.data(), ptr); fout.close(); }

    template<class T>
    friend OutParser& operator<<(OutParser& out, const T num) {
        out.putInt(num);
        return out;
    }

    friend OutParser& operator<<(OutParser& out, const char chr) {
        out.putChar(chr);
        return out;
    }

    friend OutParser& operator<<(OutParser& out, const char* str) {
        for (int i = 0; str[i]; i++)
            out.putChar(str[i]);
        return out;
    }
};


struct punct
{
    int x,y;
};

const int NMAX = 16e3 + 1;

vector<vector<int>> aint(4 * NMAX);

vector<punct> puncte;

int qst,qdr,sus,jos;

int get_posst(int x,int n)
{
    ///caut prima pozitie mai mare sau egala cu x
    int st = 0,dr = n - 1,ans = -1;
    while(st <= dr)
        {
            int mid = st + (dr - st) / 2;
            if(puncte[mid].x >= x)
                ans = mid,dr = mid - 1;
            else st = mid + 1;
        }

    if(ans == -1)
        ans = x > puncte[0].x ? n - 1 : 0;

    return ans;
}

int get_posdr(int x,int n)
{
    ///ultima pozitie mai mica sau egala cu x
    int st = 0,dr = n - 1,ans = -1;
    while(st <= dr)
        {
            int mid = st + (dr - st) / 2;
            if(x >= puncte[mid].x)
                ans = mid,st = mid + 1;
            else dr = mid - 1;
        }

    if(ans == -1) exit(69);
    return ans;
}

bool cmp(const punct &a,const punct &b)
{
    return a.x < b.x;
}

void build(int nod,int st,int dr)
{
    if(st == dr)
        {
            aint[nod].eb(puncte[st].y);
            return;
        }

    int mid = st + (dr - st) / 2;
    build(2 * nod,st,mid);
    build(2 * nod + 1,mid + 1,dr);

    ///interclasare
    int left = 2 * nod;
    int right = left + 1;
    int i = 0,j = 0,n = aint[left].size(),m = aint[right].size();
    while(i < n && j < m) aint[left][i] < aint[right][j] ? aint[nod].eb(aint[left][i++]):  aint[nod].eb(aint[right][j++]);
    while(i < n) aint[nod].eb(aint[left][i++]);
    while(j < m) aint[nod].eb(aint[right][j++]);
}

int query(int nod,int st,int dr)
{
    if(qst <= st && qdr >= dr)
        {
            int cate = upper_bound(aint[nod].begin(),aint[nod].end(),sus) - aint[nod].begin();
            cate    -= lower_bound(aint[nod].begin(),aint[nod].end(),jos) - aint[nod].begin();

            return cate;
        }

    int mid = st + (dr - st) / 2;
    int ans = 0;
    if(qst <= mid) ans += query(2 * nod,st,mid);
    if(qdr > mid) ans += query(2 * nod + 1,mid + 1,dr);

    return ans;
}

int main()
{
    InParser fin("zoo.in");
    OutParser fout("zoo.out");

    int n,q; fin >> n;
    puncte.resize(n);

    for(int i = 0; i < n ; i++)
        fin >> puncte[i].x >> puncte[i].y;

    sort(puncte.begin(),puncte.end(),cmp);
    build(1,0,n - 1);

    fin >> q;
    while(q--)
        {
            fin >> qst >> jos >> qdr >> sus;
            if(qst > puncte[n - 1].x || qdr < puncte[0].x){fout << "0\n";continue;}
            qst = get_posst(qst,n),qdr = get_posdr(qdr,n);
            fout << query(1,0,n - 1) << '\n' ;
        }
}