Cod sursa(job #2399913)

Utilizator borcanirobertBorcani Robert borcanirobert Data 8 aprilie 2019 10:25:44
Problema Cadrane Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.97 kb
#include <algorithm>
#include <iostream>
#include <fstream>
#include <vector>
#include <map>
using namespace std;

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

using VI = vector<int>;
using VVI = vector<VI>;
using VB = vector<bool>;
const int Inf = 0x3f3f3f3f;

struct Point{
    int x, y;

    bool operator < (const Point& p) const
    {
        return x < p.x;
    }
};

#define mid ((l + r) / 2 - ( l + r < 0 && (l + r) % 2 ))

class SegmTree{
public:
    SegmTree(int l, int r)
        : l{l}, r{r}, val{0}, lazy{0},
          left{nullptr}, right{nullptr}
    {
        if (l != r)
        {
            left = new SegmTree(l, mid);
            right = new SegmTree(mid + 1, r);
        }
    }

    void Update(int x, int y, int v)
    {
        Propagate();

        if (x > y)
            return;
        if (r < x || l > y)
            return;

        if (x <= l && r <= y)
        {
            lazy = v;
            Propagate();

            return;
        }

        left->Update(x, y, v);
        right->Update(x, y, v);

        val = min(left->val, right->val);
    }

    int Query(int x, int y)
    {
        Propagate();

        if (r < x || l > y)
            return Inf;
        if (x <= l && r <= y)
            return val;

        return min(left->Query(x, y), right->Query(x, y));
    }

    ~SegmTree()
    {
        if (l != r)
        {
            delete left;
            delete right;
        }
    }
private:
    void Propagate()
    {
        if (!lazy)
            return;

        val += lazy;
        if (l != r)
        {
            left->lazy += lazy;
            right->lazy += lazy;
        }

        lazy = 0;
    }

    int l, r;
    int val;
    int lazy;
    SegmTree *left, *right;
};

int N;
vector<Point> a;
VI dy, id;
map<int, VI> mp;

void ReadData();
void Solve();

int main()
{
    ReadData();
    Solve();

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

void ReadData()
{
    fin >> N;
    a = vector<Point>(N);

    for (int i = 0; i < N; ++i)
        fin >> a[i].x >> a[i].y;
    sort(a.begin(), a.end());
}

void Solve()
{
    for (const Point& p : a)
        dy.push_back(p.y);
    sort(dy.begin(), dy.end());
    dy.erase(unique(dy.begin(), dy.end()), dy.end());

    int M{(int)dy.size()};

    id = VI(N);
    for (size_t i = 0; i < a.size(); ++i)
    {
        id[i] = find(dy.begin(), dy.end(), a[i].y) - dy.begin();
        mp[a[i].x].push_back(i);
    }

    SegmTree st(0, M - 1);
    for (size_t i = 0; i < a.size(); ++i)
    {
        st.Update(0, id[i], +1);
    }

    int ans{st.Query(0, M - 1)};

    for (const auto& it : mp)
    {
        for (const int& i : it.second)
            st.Update(id[i] + 1, M - 1, +1);
        ans = max(ans, st.Query(0, M - 1));

        for (const int& i : it.second)
            st.Update(0, id[i] - 1, -1);
    }

    fout << ans << '\n';
}