Cod sursa(job #2752299)

Utilizator Razvan48Capatina Razvan Nicolae Razvan48 Data 17 mai 2021 16:51:33
Problema Zoo Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.92 kb
#include <fstream>
#include <iostream>
#include <algorithm>
#include <vector>
#include <climits>

using namespace std;

/// solutie cu aib si sortarea intervalelor dupa evenimente

const int NMAX = 16000;
const int MMAX = 100000;

vector<pair<int, int>> v;
vector<int> coordX;

int n;
int aib[1 + NMAX];

inline bool comp(pair<int, int>& a, pair<int, int>& b)
{
    return a.second < b.second;
}

struct Event
{
    int id;
    int tip; /// 1 pentru deschidere de interval, 0 pt inchidere
    int y;

    int st;
    int dr;

    Event() {};

    Event(int id, int tip, int y, int st, int dr) :
        id(id), tip(tip), y(y), st(st), dr(dr) {};

    bool operator <(const Event& other) const
    {
        return this->y < other.y;
    }
};

void update(int pos, int val)
{
    for (; pos <= n; pos += pos & -pos)
        aib[pos] += val;
}

int query(int pos)
{
    int sol = 0;

    for (; pos > 0; pos -= pos & -pos)
        sol += aib[pos];

    return sol;
}

vector<Event> events;

int sol[1 + MMAX];

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

    in >> n;

    for (int i = 1; i <= n; i++)
    {
        int x, y;

        in >> x >> y;

        v.emplace_back(x, y);
    }

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

    coordX.emplace_back(v[0].first);

    for (int i = 1; i < v.size(); i++)
    {
        if (v[i].first != v[i - 1].first)
        {
            coordX.emplace_back(v[i].first);
        }
    }

    int m;
    in >> m;

    for (int j = 1; j <= m; j++)
    {
        int x1, y1, x2, y2;

        in >> x1 >> y1 >> x2 >> y2;

        events.emplace_back(j, 1, y1 - 1, x1, x2);
        events.emplace_back(j, 0, y2, x1, x2);
    }

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

    int idx = 0;

    for (int j = 0; j < events.size(); j++)
    {
        while (idx < v.size() && v[idx].second <= events[j].y)
        {
            int pos = lower_bound(coordX.begin(), coordX.end(), v[idx].first) - coordX.begin();

            update(1 + pos, 1);
            idx++;
        }

        if (events[j].tip == 1)
        {
            int idx1 = lower_bound(coordX.begin(), coordX.end(), events[j].st) - coordX.begin() - 1;
            int idx2 = upper_bound(coordX.begin(), coordX.end(), events[j].dr) - coordX.begin() - 1;

            if (idx2 == -1) continue;

            sol[events[j].id] -= query(idx2 + 1) - query(max(idx1 + 1, 0));
        }
        else
        {
            int idx1 = lower_bound(coordX.begin(), coordX.end(), events[j].st) - coordX.begin() - 1;
            int idx2 = upper_bound(coordX.begin(), coordX.end(), events[j].dr) - coordX.begin() - 1;

            if (idx2 == -1) continue;

            sol[events[j].id] += query(idx2 + 1) - query(max(idx1 + 1, 0));
        }
    }

    for (int j = 1; j <= m; j++)
    {
        out << sol[j] << '\n';
    }

    return 0;
}