Cod sursa(job #2811322)

Utilizator cristia_razvanCristia Razvan cristia_razvan Data 1 decembrie 2021 20:40:42
Problema Zoo Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.47 kb
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
using ll = long long;

const string fn = "file";


class InParser {
private:
    FILE *fin;
    char *buff;
    int sp;

    char read_ch() {
        ++sp;
        if (sp == 4096) {
            sp = 0;
            fread(buff, 1, 4096, fin);
        }
        return buff[sp];
    }

public:
    InParser(const char* nume) {
        fin = fopen(nume, "r");
        buff = new char[4096]();
        sp = 4095;
    }

    InParser& operator >> (int &n) {
        char c;
        while (!isdigit(c = read_ch()) && c != '-');
        int sgn = 1;
        if (c == '-') {
            n = 0;
            sgn = -1;
        } else {
            n = c - '0';
        }
        while (isdigit(c = read_ch())) {
            n = 10 * n + c - '0';
        }
        n *= sgn;
        return *this;
    }

    InParser& operator >> (long long &n) {
        char c;
        n = 0;
        while (!isdigit(c = read_ch()) && c != '-');
        long long sgn = 1;
        if (c == '-') {
            n = 0;
            sgn = -1;
        } else {
            n = c - '0';
        }
        while (isdigit(c = read_ch())) {
            n = 10 * n + c - '0';
        }
        n *= sgn;
        return *this;
    }
};

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

const int mxn = 16000;
const int mxm = 100000;

struct qr {
    int xs, ys, xf, yf, i;

} qrys[mxm + 5];

struct nqr {
    int p , ys, yf, ind, tip;
    bool operator<(const nqr& oth) const {
        if (p == oth.p)
            return tip < oth.tip;
        return p < oth.p;
    }
};
vector<nqr> v;
map<int, int> mp;

int n, m;
int ans[mxm + 5];
vector<int> nrm;
vector<pair<int, int> > a;

int aib[mxn + 5];

void upd(int poz, int val) {
    for (int i = poz; i <= n + 2 * m; i += (i & (-i)))
        aib[i] += val;
}

int aibqry(int poz)
{
    int ans = 0;
    for (int i = poz; i >= 1; i -= (i & (-i)))
        ans += aib[i];
    return ans;
}

int qry2(int ys, int yf, int tip)
{
    int ans1 = 0, ans2 = 0;
    if (tip == 1)
    {
        ans1 = -aibqry(yf);
        ans2 =  aibqry(ys - 1);
    }
    else
    {
        ans1 =  aibqry(yf);
        ans2 = -aibqry(ys - 1);
    }
    return (ans1 + ans2);
}

int main() {


    fin >> n;
    a.resize(n + 1);
    a[0] = { -2e9, -2e9};
    for (int i = 1; i <= n; ++i) {
        fin >> a[i].first >> a[i].second;
        nrm.pb(a[i].second);
    }

    fin >> m;
    for (int i = 1; i <= m; ++i)
    {
        fin >> qrys[i].xs >> qrys[i].ys >> qrys[i].xf >> qrys[i].yf;
        qrys[i].i = i;
        nrm.pb(qrys[i].ys);
        nrm.pb(qrys[i].yf);
    }

    sort(nrm.begin(), nrm.end());
    for (int i = 0; i < n + 2 * m; ++i) {
        if (mp[nrm[i]] == 0)mp[nrm[i]] = i;
    }

    for (int i = 1; i <= n; ++i)
        a[i].second = mp[a[i].second];

    for (int i = 1; i <= m; ++i)
        qrys[i].ys = mp[qrys[i].ys], qrys[i].yf = mp[qrys[i].yf];

    sort(a.begin() + 1, a.end());
    for (int i = 1; i <= m; ++i)
    {
        int p1, p2;
        p1 = lower_bound(a.begin() + 1, a.end(), make_pair(qrys[i].xs, 0)) - a.begin();
        p2 = upper_bound(a.begin() + 1, a.end(), make_pair(qrys[i].xf, 0)) - a.begin();
        if (a[p2].first > qrys[i].xf)p2--;
        if (p2 == n + 1)
            p2 = n;
        if (p2 < p1)
            p2 = p1;
        nqr x;
        x.ys = qrys[i].ys;
        x.yf = qrys[i].yf;
        x.ind = i;

        x.p = p1;
        x.tip = 1;
        v.pb(x);

        x.p = p2;
        x.tip = 2;
        v.pb(x);
    }

    sort(v.begin(), v.end());


    // cout << "\n";
    // for (int i = 1; i <= n; ++i)
    // cout << a[i].second << " ";
    // cout << "\n\n\n";
    // for (auto i : v)
    // cout << i.p << " " << i.ys << " " << i.yf << " " << i.tip << " " << i.ind << "\n";

    int j = 0;
    bool tr = false;
    for (int i = 1; i <= n; ++i)
    {
        tr = false;
        while (j < m + m &&  v[j].p == i)
        {
            if (v[j].tip == 2 && !tr)
                upd(a[i].second, + 1), tr = true;
            ans[v[j].ind] += qry2(v[j].ys, v[j].yf, v[j].tip);
            // cout << j << " " << qry2(v[j].ys, v[j].yf, v[j].tip) << '\n';
            j++;
        }
        if (!tr) upd(a[i].second, + 1);
    }

    for (int i = 1; i <= m; ++i)
        fout << ans[i] << '\n';

    fin.close();
    fout.close();
    return 0;
}