Cod sursa(job #2752967)

Utilizator Razvan48Capatina Razvan Nicolae Razvan48 Data 20 mai 2021 16:37:54
Problema Zoo Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.7 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;

    v.reserve(n);

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

        in >> x >> y;

        v.emplace_back(x, y);
    }

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

    coordX.reserve(1 + n);

    int lastX = -2000000001;
    coordX.emplace_back(lastX);

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

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

    int m;
    in >> m;

    events.reserve(2 * 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)
        {
            update(v[idx].first, 1);
            idx++;
        }

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

        if (idx2 == -1) continue;

        if (events[j].tip == 1)
            sol[events[j].id] -= query(idx2) - query(idx1 - 1);
        else
            sol[events[j].id] += query(idx2) - query(idx1 - 1);
    }

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

    return 0;
}