Cod sursa(job #2399935)

Utilizator borcanirobertBorcani Robert borcanirobert Data 8 aprilie 2019 10:47:02
Problema Cadrane Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.88 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;
map<int, int> m;

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()
{
    id = VI(N);
    for (size_t i = 0; i < a.size(); ++i)
    {
        mp[a[i].x].push_back(i);
        m[a[i].y] = 0;
    }

    int M{0};
    for (auto& p : m)
        p.second = ++M;

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

      //  cout << 1 << ' ' << m[a[i].y]; cin.get();
    }

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

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

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

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